O‘zbekiston Respublikasi axborot texnologiyalari va kommunikatsiyalarni rivojlantirish vazirligi

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(n