13-ma'ruza. Np bilan bog'liq muammolar. Hisoblash qobiliyatsizligi Maruzachi o’qituvchi: katta o’qituvchi Ganihodjayeva Dilfuza Ziyavutdinovna Reja

NPC klassi (NP - to'liq topshiriqlar)

NPC (NP-complete) yoki NP-tugallangan vazifalar sinfining ta'rifi quyidagi ikkita shartni talab qiladi: birinchidan, vazifa NP sinfiga tegishli bo'lishi kerak, ikkinchidan, NP sinfidan barcha vazifalar unga ko'paytirilishi kerak.

NRS sinfi uchun quyidagi teorema isbotlandi: agar [URS polinomial echim algoritmi mavjud bo'lgan URS] sinfiga tegishli muammo bo'lsa, u holda P klassi NP klassiga to'g'ri keladi, ya'ni. P = NP

Hozirgi vaqtda yuzlab NP bilan bog'liq to'liq muammolar mavjudligi isbotlangan, ammo hozirgacha ularning hech biriga polinomial echim algoritmi topilmadi. Hozirgi vaqtda tadqiqotchilar quyidagi sinf nisbatlarini taklif qilmoqdalar: