Laboratoriya ishi 25 Mavzu: np-to’liq masalalar. Ishdan maqsad

---

LABORATORIYA ISHI - 25 
Mavzu: 
NP-to’liq masalalar.
 
Ishdan maqsad. 
NP-to’liq masalalar haqida o’rganish. 
Qo’yilgan masala.
NP-to’liq masalalar tushunchasi. 
Ish tartibi: 
•
Tajriba ishi nazariy ma’lumotlarini o‘rganish; 
•
Berilgan topshiriqning algoritmini ishlab chiqish; 
•
C++ dasturlash muhitida dasturni yaratish; 
•
Natijalarni tekshirish; 
•
Hisobotni tayyorlash va topshirish. 
Nazariy qism 
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.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. 
 
Amliy qism 
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. 
 
Topshiriqlar: 
1.
NP-tugaganligini isbotlash algoritmini tuzing. 
Nazorat savollari. 
1.
 
NP-tugaganligini isbotlash algoritmini izohlab bering. 
2.
 
Reduksiya qanday amalga oshiriladi.