Np-to‘liklik masalasi

Formal ta’rif
Alifbo deganda har qanday cheklangan belgilar to‘plami tushuniladi (masalan, {0, 1} yoki {a, b, c}). Ixtiyoriy alifbosidan tuzilgan barcha so‘zlar to‘plami (yozilgan satirlar, ushbu alifboning belgilaridan tashkil topadi) ∑* bilan belgilanadi.
∑ alfavit yordamida yaratilgan ixtiyoriy L tili bu to‘plamning L to‘plam ostisi, ya’ni L⸦ .
uchun tanib olish vazifasi berilgan so‘z tiliga tegishli yoki yo‘qligini aniqlashdir.
∑ alifbo ustida va L₂ - ikkita til bo‘lsin. L₁ tiliga (Karp bo‘yicha) L₂ tiliga qisqartirish deyiladi, agar funksiyasi mavjud bo‘lsa, bu funksiyani polinomial vaqt bilan hisoblash mumkin bo‘lsa, quyidagi xususiyatga yega: x ∈ L₁, , agar va faqat agar f(x)∈L₂, . Karp bo‘yicha qisqartirish L₁≤_pL₂ bilan belgilanadi.
Agar NP-dan biron bir til unga qisqartirilsa, L₂ tili NP-to‘liq deb nomlanadi. Til NP-mukammal deb nomlanadi, agar u NP-qiyin bo‘lsa va shu bilan birga o‘zi NP sinfida bo‘lsa.
A masala B masalasiga qisqartirilganligi, A masala B masalasidan ko‘ra “murakkabroq” ekanligini anglatadi (chunki agar biz B masalani yechilishi, A masalanini ham yechilishini bildiradi). Shunday qilib, NP bilan bog‘liq qiyinchiliklar sinfga NP bilan bog‘liq masalalar va ular uchun "ancha qiyin" bo‘lgan masalalar kiradi (ya’ni NP bilan bog‘liq masalalarni kamaytirish mumkin bo‘lgan masalalar). NP sinf NP to‘liq masalalarni va ulardan "osonroq" bo‘lgan masalalarni o‘z ichiga oladi (ya’ni, NP-to‘liq masalalarga qisqartirishgan masalalar).
Ta’rifdan shunday xulosa kelib chiqadiki, agar NP-to‘liq masalasi polinomial vaqtda hal qiladigan algoritm topilsa, unda barcha NP-to‘liq masalalar P sinfga joylashtiriladi, ya’ni ular polinomial vaqtda yechiladi.