Algoritm nazariyasiga murakkablik sinflari tushunchalarini kiritgandan so'ng, Edmonds (Edmonds, 1965) murakkablik nazariyasining asosiy muammosini qo'ydi - P = NP? Masalaning og'zaki ifodasi quyidagicha: yechimi polinom murakkabligi bilan tekshiriladigan barcha masalalarni polinom vaqtida yechish mumkinmi?
Shubhasiz, P sinfiga tegishli har qanday muammo NP sinfiga ham tegishli, chunki uni polinom bilan tekshirish mumkin - yechimni tekshirish muammosi shunchaki muammoni qayta hal qilishda bo'lishi mumkin.
P = NP masalasi
Bugungi kunga kelib, ushbu sinflarning (P = NP) mos tushishi va ularning mos tushmasligi to'g'risida nazariy dalillar mavjud emas. Taxminlarga ko'ra, P sinfi NP sinfining qism to'plamidir, ya'ni NP \ P bo'sh emas.
Masalalarning sinflar bo’yicha murakkabligi
• Agar biron bir algoritm natija - X massivini keltiradigan bo'lsa, unda bu natijaning to'g'riligini tekshirish polinom murakkabligi bilan amalga oshirilishi mumkin: ∑= V ni tekshirish uchun Q (n) dan ortiq bo’lmagan operatsiyalar talab qilinadi.
• Rasmiy ravishda: ∀ D∈, |D| = n biz S∈ sertifikatini beramiz, shunday qilib |S| = O () algoritm va = (D, S), agar u to'g'ri bo'lsa "1", agar yechim noto'g'ri bo'lsa "0“ natija beradi. Unda F () = O () bo'lsa, muammo NP sinfiga tegishli.
• Aslida, muammo NP sinfiga tegishli bo'lsa, uning qandaydir algoritm bilan yechimi tez (polinomial) tekshirilishi mumkin bo’lsa.
E’TIBORINGIZ UCHUN RAXMAT!
http://fayllar.org
Do'stlaringiz bilan baham: |
