Mavzu: p va np sinflari. Np to’liq masala tushunchasi

Mavzu: P va NP sinflari. NP to’liq masala tushunchasi

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.

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

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.

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.

Download 46.91 Kb.