Zo'r NP to'liqligi - Weak NP-completeness
Yilda hisoblash murakkabligi, an To'liq emas (yoki Qattiq-qattiq ) muammo zaif NP bilan to'ldirilgan (yoki zaif NP-hard), agar mavjud bo'lsa algoritm ish vaqti bo'lgan muammo uchun polinom muammo o'lchovida va ma'lumotlarning kattaligida (agar ular berilgan bo'lsa) butun sonlar ), taglik-ikkita o'rniga logarifmlar ularning kattaligi. Bunday algoritmlar texnik jihatdan eksponent ularning kirish hajmining funktsiyalari va shuning uchun hisobga olinmaydi polinom.
Masalan, NP-hard xalta muammosi tomonidan hal qilinishi mumkin dinamik dasturlash xalta kattaligi va buyumlar sonida bir nechta polinom bosqichlarini talab qiluvchi algoritm (barcha ma'lumotlar butun son sifatida o'lchangan deb faraz qilingan); ammo, ushbu algoritmning ishlash muddati eksponent vaqt ob'ektlar va ryukzakning kirish kattaligi ularning kattaligi bo'yicha logaritmikdir. Biroq, Garey va Jonson (1979) kuzatganidek, "A psevdo-polinomial vaqt algoritm… bizni qiziqtirgan ilova uchun kamdan-kam bo'lishi mumkin bo'lgan "haddan tashqari katta" raqamlarni o'z ichiga olgan holatlarga duch kelganda "eksponent xatti-harakatlarni" aks ettiradi. Agar shunday bo'lsa, ushbu turdagi algoritm bizning maqsadlarimizga deyarli xizmat qilishi mumkin polinom vaqt algoritmi ”. NP-ning to'liq bajarilmagan muammosi uchun yana bir misol pastki yig'indisi muammosi.
Bilan bog'liq atama kuchli NP bilan to'ldirilgan (yoki unary NP-to'liq) ma'lumotlar kodlangan bo'lsa ham, NP-ni to'ldiradigan muammolarni anglatadi. unary (ya'ni ma'lumotlar umumiy kirish hajmiga nisbatan "kichik" bo'lsa).
Adabiyotlar
- M. R. Garey va D. S. Jonson. Kompyuterlar va bajarilmaslik: NP to'liqligi nazariyasi bo'yicha qo'llanma. W.H. Friman, Nyu-York, 1979 yil.
- L. Xoll. Hisoblash murakkabligi. Jons Xopkins universiteti.