Reja p va np sinflar muammosi. Muammo np-tugaganligini isbotlash

NP-tolgan 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 boto (berilgan dastur berilgan kirishda tolgan masalalar mavjud, har qanday bunday algoritm uzoq vaqt ishlaydi la olmadi.

Agar biz amaliy algoritmlar va faqat nazariy qiziqish algoritmlari opol, ammo rasmiy chegara chizishni istasak, unda korinda turadi. NP -torib chiqamiz. Ushbu masalalar uchun hech qanday polinomial' algoritmlar topilmagan, ammo bunday algoritmlar mavjud emasligi isbotlanmadi. NP bilan bogrganish deb nomlangan savol bilan bogrtasida qoplikli vaqt ichida ishlaydigan algoritmlar sinfi birinchi oliq deb nomlangan masalalar sinfini koliq muammolarni oP = NPliq. Bu savol 1971 yilda berilgan va hozirda hisoblash nazariyasida eng qiyin masalalardan biri hisoblanadi.

Nima uchun dasturchi NP toliqligini isbotlash mumkin bolmaydi deb hisoblash uchun asos bor. Bunday holda, uni aniq hal qiladigan tezkor algoritmni qidirishni davom ettirishdan koliqlik masalasining kuchlilik tomoni

• Agar masalaning qisim masalalari mavjud boliq masala deyiladi, bunda: Masalaning raqamli parametrlari mavjud bolmasa (ya'ni, bu masalada uchraydigan kattaliklarning maksimal' qiymati polinom uzunligi bilan yuqoridan chegaralangan).
• NP-to NP gipotezasi tori boliqlik masalaga misollar

• Bul' formulalari bajarilishi masalasi
• "Doglchamining eng qisqa yechimi
• Kommivoyajyora masalasi
• Shteyner muammosi
• Grafani boplamni qoplash masalasi
• Tanlash masalasi
• Toyin)
• Tetris