O‘zbekiston Respublikasi axborot texnologiyalari va kommunikatsiyalarni rivojlantirish vazirligi

---

O‘zbekiston Respublikasi axborot texnologiyalari va 
kommunikatsiyalarni rivojlantirish vazirligi 
 
 
Muhammad Al-Xorazmiy nomidagi Toshkent axborot 
texnologiyalari universiteti Elektron tijorat fakulteti 010-20 
sirtqi guruh talabasi Raxmatov Shoxjaxoning Algoritmarni 
loyihalash fanidan bajargan 
 
Mustaqil ishi 
 
 
Bajardi: Raxmatov Shoxjaxon 
 
 
 
Toshkent-2023 
 

---

Reja: 
1. P va NP sinflar muammosi. 
2. Muammo NP-tugaganligini isbotlash 
3. 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 
keyingi 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 ”.