Texnologiyalari universiteti mustaqil ish

---

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT 
TEXNOLOGIYALARI UNIVERSITETI 
 
 
 
 
 
MUSTAQIL ISH 
Mavzu: P va NP sinflari. NP to’liq masala tushunchasi. 
 
 
 
 
 
Bajardi: 051-19 guruh ta`labasi
Abduolimov A. A.
Tekshirdi: Mamadaliyev X. A.
 
 
 
 
 
 
TOSHKENT 2022

---

P va NP sinflari. NP to’liq masala tushunchasi. 
Reja: 
P va NP sinflar muammosi. 
Muammo NP-tugaganligini isbotlash 
NP to’liq masala tushunchasi 
P va NP muammosi 
Har bir informatika talabasi P va NP muammolari haqida eshitishi kerak. Aytish 
mumkinki, bu kompyuter fanidagi eng mashhur echimsiz muammo. Clay 
Matematika Instituti tomonidan tanlangan 7 ming yillik mukofot muammosidan biri, 
birinchi to'g'ri echim uchun 1 million dollar mukofotni olib yurish va hozir ham 
ochiq. P = NP muammosini isbotlash yoki echish informatika, matematika, 
kriptografiya, AI, multimedia ishlov berish, iqtisodiyot va boshqa sohalarda chuqur 
ta'sir ko'rsatishi mumkin. Ushbu muammo noaniq tarzda aytilishi mumkin 
"Kompyuter tomonidan tezda tekshirilishi mumkin bo'lgan har qanday muammoni 
kompyuter ham tezda hal qiladimi?". 
Garchi bu masalaning mavjudligi 1950-yillarda Jon Nesh va Kurt Godel tomonidan 
muhokama qilingan bo'lsa-da, ushbu muammoni 1971 yilda Stefan Kuk o'zining 
mashhur "Teoremalarni tayyorlash protseduralarining murakkabligi" nomli 
maqolasida rasmiy ravishda kiritgan. Rasmiy bayonotga va muammoni 
tushuntirishga sho'ng'ishdan oldin, avval mavzu bilan bog'liq ba'zi ta'riflarni ko'rib 
chiqamiz. 
Tegishli atamalar va ta'riflar: - 
Yuqoridagi noaniq bayonotda ishlatiladigan kompyuter so'zi Deterministik Turing 
Machine (DTM) ga tegishli. Oddiy so'z bilan aytganda, bu faqat bitta keying 
bosqichga o'tishni tanlashi mumkin bo'lgan mashina. Dallanmagan mashina [3]. Har 
bir mavjud kompyuter shunday ishlaydi. 
Polinom 
- 
ba'zi 
kuchlarga 
va 
ularning 
koeffitsientlariga 
ko'tarilgan 
o'zgaruvchilardan tashkil topgan ibora. Masalan, ax² + bx + c shaklidagi ikkinchi 
darajali ko'paytma. 
Algoritm vaqt murakkabligi - kirishning uzunligi funktsiyasi sifatida bajarilishi 
uchun algoritm olgan vaqt. Katta O belgi yordamida umumiy ifodalanadi. Masalan, 
2n o'lchamdagi barcha elementlarni birma-bir bosib chiqarish uchun algoritm 
yozsak, uning vaqt murakkabligi O (n) bo'ladi. 

---

Polinomial vaqt murakkabligi - algoritmning vaqt murakkabligi n ^ {O (1)} 
P = Deterministik Turing mashinasi tomonidan ko'paytirilgan vaqt ichida 
echiladigan muammolar to'plami. 
NP = noaniq bo'lmagan polinomik vaqt ichida yechilishi mumkin bo'lgan echimlar 
muammolarining to'plami (javob ha yoki yo'q) i.e ko'p bo'lmagan vaqt ichida 
noaniqsiz Turing Machine [4] tomonidan hal qilinishi mumkin. 
Nondeterministic Turing Machine (NTM) - dallanadigan mashina. Agar 
hisoblashning keyingi bosqichi uchun ko'plab imkoniyatlar mavjud bo'lsa, ushbu 
mashina ularning barchasini bir vaqtning o'zida o'chirib qo'yishi mumkin. NTM-lar 
O (1) vaqtda ko'p variantlardan to'g'ri variantni taxmin qilishga qodir. 
NPga alternativ ta'rif bu mumkin bo'lgan echim taqdim etilsa, DTM polinomik vaqt 
ichida uning to'g'riligini tekshirishga imkon beradigan qarorlar to'plamidir. Shuni 
ta'kidlash kerakki, barcha P muammolar NP ga ham tegishli, chunki agar muammo 
DTM tomonidan ko'p martali hal qilinsa, mumkin bo'lgan echimni tekshirish hal 
qilishdan osonroq bo'ladi. Shunday qilib, DTM ham ko'plik vaqt ichida ham 
tekshirishi mumkin edi. Shunday qilib, arzimas, P 
⊆
NP i.e P NP ning pastki qismi. 
Bugungi kunda mavjud bo'lgan barcha kompyuterlar DTM va NTM fikrlash 
tajribalarida ishlatiladigan sof nazariy kompyuter ekanligini bilish ham muhimdir. 
Professor Erik Demain aytganidek [1]. 
"Demak, bu (NTM) ancha kuchli model. Albatta, bunday ishlaydigan kompyuterlar 
yo'q, afsuski, men ko'proq qiziqayapman ”. 
Ko'proq atamalar va ta'riflar: - 
NP-qiyin - agar X 
∈
NP X-ga tushadigan bo'lsa, X muammosi kamida NPda hal 
qilinadi, masalan NP-ning har bir muammosini hal qilish qiyin (agar P! = NP bo'lsa, 
unda X P ga tegishli bo'lmaydi). 
Reduksiya - A muammoni kiritishlarni ko'paytma vaqt algoritmidan foydalanib, B 
muammosining ekvivalent kirishiga aylantirish jarayoni. Ekvivalent degani, A va B 
muammolari kirish va o'zgartirilgan kirish uchun bir xil javobni (Ha yoki Yo'q) 
berishi kerak. A dan B gacha qisqartirish algoritmining mavjudligi quyidagilarni 
nazarda tutadi: 

---

1. Agar B 
∈
P bo'lsa, u holda A 
∈
P (ko'paytmali vaqt ichida A dan B gacha 
qisqartirishingiz mumkin va B polinomik vaqt ichida echishingiz mumkin. Buni 
birlashtirish A uchun ko'p vaqtli algoritmni beradi) 
2. Agar B 
∈
NP bo'lsa, unda A 
∈
NP 
3. Agar A NP-qattiq bo'lsa, B - NP-qattiq. A ko'paytirilgan vaqt ichida B ga 
kamayishi mumkin va agar B NP-qiyin bo'lmasa, u B B NP-NP-qiyin va bu A 
∈
NP-
NP-qattiq, bu farazga zid (A-NP-qiyin) degan ma'noni anglatadi. 
NP-to'liqligi - agar X 
∈
NP va X bo'lsa, NP-qiyin bo'lsa, X muammo NP-tugallanadi. 
Muammo NP-tugaganligini isbotlash 
Muammoning to'liqligini isbotlash 2 bosqichni o'z ichiga oladi. Avval biz muammo 
NPga tegishli ekanligini ko'rsatishimiz kerak va keyin biz buni NP-qiyinligini 
ko'rsatishimiz kerak. Bosqichlarni quyidagicha izohlash mumkin: 
1-qadam - X 
∈
NP ni ko'rsatish. X uchun netereterministik algoritmni toping. Ammo 
amaliy usul, agar potentsial echim taqdim etilsa, X uchun ko'paytmali vaqt 
tekshiruvini o'tkazishdir. 
2-qadam - X-ni ko'rsatish qiyin emas. Ma'lum NP-muammoni X-ga qisqartirish. 
Demak, biz ko'rgan 3-rasm orqali X bu NP-qiyin ekanligini anglatadi. 
Bu 
masala 
qisqa 
P 
va 
NP 
murakkab 
sinfi 
tengmi? 
P-sinfi deb kompyuter “tezda”(“Birzumda”) yechimi mumkin bo’lgan masalalar 
majmuiga aytiladi. Bunga arifmetik amallarning asosi (negizi) ro’yhatlarni saralash, 
jadval 
bo’yicha 
ma’lumotlarni 
izlash 
kiradi. 
NP-sinfiga javobning to’g’riligini tezda tekshirish mumkin bo’lgan masala kiradi. 
Masalan: faraz qilaylik sizda qiymati 2,3,5,6 va 7 so’mlik tangalardan bittadan bor 
va siz narxi 21 so’m bo’lgan harid uchun qaytimsiz to’lashni hoxlamoqdasiz. 
Ulardan yig’indisi 21 so’m bo’lgan tangalarni yig’ib olish mumkinmi? 
Bu masalaga javob olish uchun har hil variantni tanlash lozim, agar masala 
yechimini yo’qligini isbotlasmoqchi bo’lsak, umuman olganda barcha bo’lishi 
mumkin bo’lgan variantlardni tanlash lozim. Agar tangalar sonini bir necha usulda 
ko’paytirsak yechish mutlaqo nomuvofiq ko’rinishda bo’ladi. Bunda natijani oson 
tekshirish uchun shunchaki barcha “ming yillik masalasi” ning mohiyati 
quyidagicha (bunday) ifodalanadi (ta’riflanadi): P va NP sinflari tengmi? Agar 
masala yecvhimining to’g’riligini tekshirish oson bo’lsa, masalani o’zini yechish 
ham 
oson 
bo’lishi 
mumkinmi? 
Ko’pchilik mutaxassislar javobning yo’qligi (salbiy)ga amindirlar, lekin buni 

---

hozircha hech kim isbotlay olgani yo’q agar P=NP bo’lib qolsa, unda insoniyatni 
kriptografiyaga (sirli belgi va ishoralar bilan yozish tizimi) keskin burilish ko’taradi. 
NP-to’liqlik masalasi 
Amaliy nuqtai nazardan qiziq bo‘lgan vazifalarning aksariyati, polinomial' 
(polinomial' vaqt mobaynida ishlovchi) algoritmlar. Ya'ni, n uzunlikdagi kirishda 
algoritmning ishlash vaqti doimiy k (kirish uzunligidan mustaqil) uchun O(nk) dan 
oshmaydi. Har bir masalada ushbu xususiyatni qondiradigan yechim algoritmi 
mavjud emas. Ba'zi masalalarni umuman biron bir algoritm yordamida hal qilib 
bo‘lmaydi. Bunday masalaning klassik misoli bu “to‘xtash muammosi” (berilgan 
dastur berilgan kirishda to‘xtashini bilish). Bundan tashqari, ularni hal qiladigan 
algoritm mavjud bo‘lgan masalalar mavjud, har qanday bunday algoritm uzoq vaqt 
ishlaydi – uning ishlash vaqti har qanday fiksirlangan k soni uchun O(nk) bo‘la 
olmadi. 
Agar biz amaliy algoritmlar va faqat nazariy qiziqish algoritmlari o‘rtasida qo‘pol, 
ammo rasmiy chegara chizishni istasak, unda ko‘plikli vaqt ichida ishlaydigan 
algoritmlar sinfi birinchi o‘rinda turadi. NP -to‘liq deb nomlangan masalalar sinfini 
ko‘rib chiqamiz. Ushbu masalalar uchun hech qanday polinomial' algoritmlar 
topilmagan, ammo bunday algoritmlar mavjud emasligi isbotlanmadi. NP bilan 
bog‘liq muammolarni o‘rganish “P = NP” deb nomlangan savol bilan bog‘liq. Bu 
savol 1971 yilda berilgan va hozirda hisoblash nazariyasida eng qiyin masalalardan 
biri hisoblanadi. 
Nima uchun dasturchi NP – tugallangan masalalar haqida bilishi kerak? Agar biron 
bir NP – to‘liqlik uchun uning to‘liqligini isbotlash mumkin bo‘lsa, uni deyarli hal 
qilib bo‘lmaydi deb hisoblash uchun asos bor. Bunday holda, uni aniq hal qiladigan 
tezkor algoritmni qidirishni davom ettirishdan ko‘ra, taxminiy algoritmni tuzishga 
vaqt sarflash yaxshiroqdir. 
Polinom vaqti. Abstrakt masalalar 
Yuqorida aytib o‘tilganidek, ko‘p jihatdan hal qilinadigan (polinomial) masalalar 
konsepsiyasi amalda yechilishi mumkin bo‘lgan masalalar g‘oyasini 
takomillashtirish hisoblanadi. Ushbu kelishuvni nima tushuntiradi? Birinchidan, 
amalda ishlatiladigan ko‘paytirilgan algoritmlar, odatda juda tez ishlaydi. 
Ikkinchidan, polinomial algoritmlar sinfini ko‘rib chiqish, bu sinfning hajmi ma'lum 
bir hisoblash modelini tanlashdan deyarli mustaqil bo‘lishidir. Masalan, tasodifiy 
tasodifiy kirish mashinasida (RAM) ko‘paytirilgan vaqt ichida yechilishi mumkin 
bo‘lgan masalalar sinfi T'yuring mashinalarida polinomal yechiladigan masalalar 
sinfiga to‘g‘ri keladi. Sinf parallel hisoblash modeli uchun bir xil 
bo‘ladi, prosessorlar soni, kirish uzunligi polinomi bilan cheklangan. Uchinchidan, 
polinomal yechiladigan masalalar sinfi tabiiy yopiqlik xususiyatlariga ega. Masalan, 

---

ikkita algoritmning tarkibikompozisiyasi ham polinomial vaqtli ishlaydi. Buning 
sababi, ko‘pxadlarning yig‘indisi, ko‘paytmasi va kompozisiyasi ko‘pxadrdir. 
Quyida hisoblash masalasining abstrakt modelini keltirilgan. Buni abstrakt masala 
deb nomlaymiz, Q – ikkita to‘plam elementlari orasidagi ixtiyoriy binar munosabat: 
I – shartlar to‘plami va S – yechimlar to‘plami. Masalan, G=(V,E) yo‘naltirilmagan 
grafning berilgan ikkita uchlari orasidagi eng qisqa yo‘lni topish masalasida, shart 
(element I) uch element, graf va ikkita qirradan iborat va yechim (S element) – bu 
grafda kerakli yo‘lni tashkil etuvchi vertikallarning ketma-ketligi. 
NP to‘liqligi nazariyasida faqat hal qilish masalalari ko‘rib chiqiladi – muayyan 
savolga “ha” yoki “yo‘q” deb javob berish kerak bo‘lgan masalalar. Rasman, I 
to‘plam shartlarini {0,1} to‘plamga to‘g‘ri keladigan funksiya sifatida ko‘rib 
chiqilishi mumkin. Masalan, G=(V,E) grafdagi eng qisqa yo‘lni topish masalasi 
bilan berilgan G=(V,E) graf yordamida ikkita tugun u, v
∈
V va natural k butun sonlar 
u va v tugunlari orasida undan katta bo‘lmagan hamda G grafda yo‘l bor yoki 
yo‘qligi masalasini yeching. 
Optimallashtirish bilan bog‘liq masalalar bu – muayyan miqdordagi qiymatni 
maksimal darajada oshirish yoki minimallashtirish kerak bo‘lgan masalalardi. NP – 
to‘liqlik haqida savol berishdan oldin bunday masalalar, ularni hal qilish 
masalalariga aylantirilishi kerak. Shunday qilib, masalan, grafdagi eng qisqa yo‘lni 
topish masalasida optimallashtirish masalasini yechish masalasidan ruxsat berish 
masalasiga o‘tdik va yo‘l uzunligiga cheklov qo‘shdik. Agar transformasiyadan 
keyin NP – to‘liq masalasi yuzaga kelsa, unda asl muammoning qiyinligi ham 
belgilanadi. Ma'lumotlar taqdimoti 
Kirish ma'lumotlarini (ya'ni I to‘plamning elementi) algoritmga kiritishdan oldin 
ularning qanday qilib “kompyuterga qulay” tarzda taqdim etilishi to‘g‘risida kelishib 
olish kerak. Dastlabki ma'lumotlar bitlar ketma-ketligi bilan kodlangan deb qabul 
qilamiz. Formal aytganda, S to‘plamining elementlarini ifodalash bu S dan e ni bitli 
satrlar to‘plamlariga tushishidir. Masalan, (0, 1, 2, 3,...) – butun sonlarni, odatda (0, 
1, 10, 11, 100, ...) – bitli satrlar bilan ifodalanadi. 
Taqdim qilingan ma'lumotlarni joylashtirb, mavhum masalani satrli ma'lumotga 
aylantiramiz, bu satirli ma'lumot uchun kirish ma'lumotlari, masalaning dastlabki 
ma'lumotlarini aks ettiruvchi bitli satir bo‘ladi. Kirish ma'lumotlari (bitli satr) n – 
uzunlikda bo‘lganida, algoritmning ishlash vaqti O(T(n)) – bo‘lsa, algoritm satirli 
masalani O(T(n)) vaqtda yechadi desak bo‘ladi. Agar k konstanta va O(T(n)) vaqt 
ichida bu masalani yechadigan algoritm mavjud bo‘lsa, satirli masala polinomial' 
deb ataladi. Murakkablik P sinfi – bu barcha satirli masalalar bo‘lib, polonomia' vaqt 
ichida yechilishi mumkin, ya'ni, O(nk) vaqt ichida yechilishi mumkin, bu yerda k 
kirishga bog‘liq bo‘lmaydi. 

---

Polinomial abstrakt masalasining konsepsiyasini aniqlashni istagan holda, biz turli 
xil ma'lumotlarni taqdim etish mumkinligiga duch kelamiz. 
Xar bir taqdim qilingan e to‘plam uchun, I kirishlari bo‘lgan Q abstrakt masalaning 
satirli masalasini olamiz. 
Biroq, amalda (asosi 1 bo‘lgan raqamli tizim kabi “qimmat” vakillik usullarini 
istisno qilsak), tabiiy vakillik usullari odatda ekvivalentdir, chunki ularni bir-biriga 
ko‘p jihatdan aylantirish mumkin. A polinomial algoritmi mavjud 
bo‘lsa, f:{0,1}*→{0,1}* funksiyasi polinimial vaqt ichida hisoblab chiqiladi, u har 
qanday x
∈
{0,1}* uchun f(x) natijani beradi. 
Ixtiyoriy abstrakt masala uchun I to‘plami sharitlarini ko‘rib chiqamiz. I 
to‘plamning е1 va е2 elementlari polinomial' bog‘langan deyiladi, agar polinomial' 
vaqtda hisoblash mumkin bo‘lgan ikkita f12(e1(i)) = e2(i) va f21(e2(i)) 
= e1(i), i 
∈
I funsiyalar mavjud bo‘lsa. Bunday hollarda, polinomial' bog‘langan 
ikkita elementdan qaysi birini tanlash muhim emas. 
P, NP, NP-complete (NP-to‘liklik masalalari) sinflar orasidagi munosabatlar, NP-
hard (NP-murakkab masalalar), P≠NP va P=NP bo‘lgan xollarda. 
NP- tuliklik masalasi — algoritmlar nazariyasida NP – sinfdagi «ha» yoki «yo‘k» 
javobli masalani shu sinfdagi boshka masalaga polinomial' vakt oralgida 
moslashtirish mumkin (yani, boshlangich ma'lumotlar xajmiga boglanganlik 
darajasi ma'lum polinimdan katta bulmagan amallar yordamida bajariladi). 
Shunday qilib, NP -to‘liq masalalar, ma'lum ma'noda, NP sinfidagi “tipik” masalalar 
to‘plamini shakllantiradi: agar ularning ba'zilari uchun "tezkor" yechim algoritmi 
topilsa, NP sinfidagi har qanday boshqa masalani xuddi shu tarzda hal qilish 
mumkin. 
Formal' ta'rif 
Alifbo deganda har qanday cheklangan belgilar to‘plami tushuniladi (masalan, {0, 
1} yoki {a, b, c}). Ixtiyoriy ∑ alifbosidan tuzilgan barcha so‘zlar to‘plami (yozilgan 
satirlar, ushbu alifboning belgilaridan tashkil topadi) ∑* bilan belgilanadi. 
∑ alfavit yordamida yaratilgan ixtiyoriy L tili bu ∑^* to‘plamning L to‘plam ostisi, 
ya'ni L⸦∑^*. 
L uchun tanib olish vazifasi berilgan so‘z L tiliga tegishli yoki yo‘qligini aniqlashdir. 
∑ alifbo ustida va - ikkita til bo‘lsin. tiliga (Karp bo‘yicha) L2 tiliga qisqartirish 
deyiladi, agar funksiyasi mavjud bo‘lsa, bu funksiyani polinomial' vaqt bilan 

---

hisoblash mumkin bo‘lsa, quyidagi xususiyatga yega: : x 
∈
L1, , agar va faqat agar . 
Karp bo‘yicha qisqartirish L1≤pL2 bilan belgilanadi. 
Agar NP-dan biron bir til unga qisqartirilsa, tili NP-to‘liq deb nomlanadi. Til NP-
mukammal deb nomlanadi, agar u NP-qiyin bo‘lsa va shu bilan birga o‘zi NP sinfida 
bo‘lsa. 
A masala B masalasiga qisqartirilganligi, A masala B masalasidan ko‘ra 
“murakkabroq” ekanligini anglatadi (chunki agar biz B masalani yechilishi, A 
masalanini ham yechilishini bildiradi). Shunday qilib, NP bilan bog‘liq 
qiyinchiliklar sinfga NP bilan bog‘liq masalalar va ular uchun "ancha qiyin" bo‘lgan 
masalalar kiradi (ya'ni NP bilan bog‘liq masalalarni kamaytirish mumkin bo‘lgan 
masalalar). NP sinf NP to‘liq masalalarni va ulardan "osonroq" bo‘lgan masalalarni 
o‘z ichiga oladi (ya'ni, NP-to‘liq masalalarga qisqartirishgan masalalar). 
Ta'rifdan shunday xulosa kelib chiqadiki, agar NP-to‘liq masalasi polinomial' vaqtda 
hal qiladigan algoritm topilsa, unda barcha NP-to‘liq masalalar P sinfga 
joylashtiriladi, ya'ni ular polinomial' vaqtda yechiladi. 
NP-to‘liqlik masalasining kuchlilik tomoni 
Agar masalaning qisim masalalari mavjud bo‘lsa u kuchli NP-to‘liq masala deyiladi, 
bunda: Masalaning raqamli parametrlari mavjud bo‘lmasa (ya'ni, bu masalada 
uchraydigan kattaliklarning maksimal' qiymati polinom uzunligi bilan yuqoridan 
chegaralangan). 
Masalaning raqamli parametrlari mavjud bo‘lmasa (ya'ni, bu masalada uchraydigan 
kattaliklarning maksimal' qiymati polinom uzunligi bilan yuqoridan chegaralangan). 
NP-to‘liqlik masala. 
Bunday vazifalar sinfi NPCS deb nomlanadi. Agar P ≠ NP gipotezasi to‘g‘ri bo‘lsa, 
unda NPCS masalasi uchun soxtaopolinomial algoritm mavjud emas. 
NP-to‘liqlik masalaga misollar 
Bul' formulalari bajarilishi masalasi 
"Dog‘lar" n × n o‘lchamining eng qisqa yechimi 
Kommivoyajyora masalasi 
Shteyner muammosi 
Grafani bo‘yash masalasi 
Soxa (yuza) qoplamasi masalasi 
To‘plamni qoplash masalasi 

---

Tanlash masalasi 
To‘plamning mustaqilligi masalasi 
Saper (o‘yin) 
Tetris 
Adabiyotlar 
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: 
Мир, 1982. 
Томас Х. Кормен и др. Боб. 34 NP-полнота // Алгоритмы: построение и анализ 
= Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — 1296 с. 
— ISBN 0-07-013151-1. 
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию 
автоматов, языков и вычислений = Introduction to Automata Theory, Languages, 
and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1. 
Internet saytlari: 
https://en.wikipedia.org/wiki/P_versus_NP_problem 
http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2025%20-
%20P%20and%20NP.htm 
https://uz.wikipedia.org/