NP-to'liq muammo nima ekanligini eslaysizmi? U oddiy NP dan qanday farq qiladi?

NP (nondeterministic polynomial time) — bu polinom vaqt ichida tekshirilishi mumkin bo'lgan vazifalar sinfidir. Ya'ni, agar sizda javob uchun nomzod bo'lsa, uni tezda to'g'ri yoki noto'g'ri ekanligini tekshirishingiz mumkin.

NP to'liq vazifalar — bu NP ning kichikroq to'plami bo'lib, ular shu sinfda eng "qiyin" bo'lib hisoblanadi. Agar kimdir har qanday NP to'liq vazifaning polinom algoritmini topgan bo'lsa, unda barcha NP vazifalarini polinom vaqt ichida hal qilish mumkin bo'ladi.

Asosiy farq:

• NP — tezda tekshirilishi mumkin bo'lgan vazifalar.
• NP to'liq — NP ichidagi vazifalar, ular boshqa har qanday NP vazifasiga kamaytirilishi mumkin (ya'ni, ular "eng murakkab" bo'lib hisoblanadi).

Misol: grafiga maksimal klika muammosi NP to'liq, va elementlar to'plamining yig'indisi berilgan raqamga tengligini tekshirish muammosi NP da.