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

P va E sinflariga tayinlanishi mumkin bo'lmagan vazifalar.

• Deterministik bo'lmagan Turing mashinasi polinomial vaqt ichida hal qila oladigan muammolar, deterministik Turing mashinasida esa polinom algoritmi noma'lum.

• Ushbu vazifalar uchun samarali (ya'ni ko'paytirilgan) algoritm hali ishlab chiqilmagan, ammo bunday algoritmlar mavjud emasligi isbotlanmagan.

• KP klassi ko'p sonli vaqt ichida hal qilinishi mumkin bo'lgan barcha muammolarni o'z ichiga oladi. Oracle tekshiruvchisi tomonidan ko'p vaqtli vaqt ichida tekshirilgandan so'ng "qonuniy" kuchga ega bo'lgan echimlarni taklif qiladi.

Bir misol.

Berilgan n sonlar a1, ... va V. soni. Muammo: vektorni (massiv) X = (x1, ..., xn), xi E {0,1} toping, shunday qilib ∑aixi = V.

I.e. Y sonini A massivining har qanday elementlari yig'indisi sifatida ifodalash mumkinmi.

Agar ba'zi bir algoritm natijani keltirib chiqarsa - X massivi, unda bu natijaning to'g'riligini tekshirish ko'paytirilgan murakkablik bilan bajarilishi mumkin: aixi = V ni tekshirish O (N) operatsiyalarni talab qiladi.