O‘zbekiston Respublikasi axborot texnologiyalari va kommunikatsiyalarni rivojlantirish vazirligi

k
) vaqt ichida yechilishi mumkin, bu 
yerda k kirishga bog‘liq bo‘lmaydi. 
Polinomial abstrakt masalasining konsepsiyasini aniqlashni istagan holda, biz turli 
xil ma'lumotlarni taqdim etish mumkinligiga duch kelamiz.
Xar bir taqdim qilingan e to‘plam uchun, I kirishlari bo‘lgan Q abstrakt masalaning 
satirli masalasini olamiz. 
Biroq, amalda (asosi 1 bo‘lgan raqamli tizim kabi “qimmat” vakillik usullarini 
istisno qilsak), tabiiy vakillik usullari odatda ekvivalentdir, chunki ularni bir-biriga 
ko‘p jihatdan aylantirish mumkin. A polinomial algoritmi mavjud bo‘lsa, 
f:{0,1}*→{0,1}* funksiyasi polinimial vaqt ichida hisoblab chiqiladi, u har qanday 
x
∈ {0,1}* uchun f(x) natijani beradi. 
Ixtiyoriy abstrakt masala uchun I to‘plami sharitlarini ko‘rib chiqamiz. I 
to‘plamning е1 va е2  elementlari polinomial' bog‘langan deyiladi, agar 
polinomial' vaqtda hisoblash mumkin bo‘lgan ikkita f
12
(e
1
(i)) = e
2
(i) va f
21
(e
2
(i)) = 
e
1
(i), i 
∈ I funsiyalar mavjud bo‘lsa. Bunday hollarda, polinomial' bog‘langan 
ikkita elementdan qaysi birini tanlash muhim emas. 
P, NP, NP-complete (NP-to‘liklik masalalari) sinflar orasidagi munosabatlar, NP-
hard (NP-murakkab masalalar), P≠NP va P=NP bo‘lgan xollarda. 
NP- tuliklik masalasi — algoritmlar nazariyasida NP – sinfdagi «ha» yoki «yo‘k» 
javobli masalani shu sinfdagi boshka masalaga polinomial' vakt oralgida 
moslashtirish mumkin (yani, boshlangich ma'lumotlar xajmiga boglanganlik 
darajasi ma'lum polinimdan katta bulmagan amallar yordamida bajariladi). 
Shunday qilib, NP -to‘liq masalalar, ma'lum ma'noda, NP sinfidagi “tipik” 
masalalar to‘plamini shakllantiradi: agar ularning ba'zilari uchun "tezkor" yechim 
algoritmi topilsa, NP sinfidagi har qanday boshqa masalani xuddi shu tarzda hal 
qilish mumkin. 
Formal' ta'rif
Alifbo deganda har qanday cheklangan belgilar to‘plami tushuniladi (masalan, {} 
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⸦∑^*. 
L uchun tanib olish vazifasi berilgan so‘z L tiliga tegishli yoki yo‘qligini aniqlashdir. 
∑ alifbo ustida 𝐿
1
va - ikkita til bo‘lsin. 𝐿
1
tiliga (Karp bo‘yicha) L
2
tiliga 
qisqartirish deyiladi, agar
𝑓: ∑
∗ 
→ ∑
∗
funksiyasi mavjud bo‘lsa, bu funksiyani 
polinomial' vaqt bilan hisoblash mumkin bo‘lsa, quyidagi xususiyatga yega: : 
𝑥 ⋴ 𝐿
1
, agar va faqat agar 
𝑓(𝑥) ⋴ 𝐿
2
. Karp bo‘yicha qisqartirish L
1
≤
p
L
2 
bilan 
belgilanadi. 

---

Agar NP-dan biron bir til unga qisqartirilsa, 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.