Texnalogiyalari universiteti 030-20 guruh talabasi Xayridinov Vohidjonning

Ko'proq atamalar va ta'riflar: - 
• 
NP-qiyin - agar X ∈ NP X-ga tushadigan bo'lsa, X muammosi kamida NPda hal 
qilinadi, masalan NP-ning har bir muammosini hal qilish qiyin (agar P! = NP 
bo'lsa, unda X P ga tegishli bo'lmaydi). 
• 
Reduksiya - A muammoni kiritishlarni ko'paytma vaqt algoritmidan foydalanib, B 
muammosining ekvivalent kirishiga aylantirish jarayoni. Ekvivalent degani, A va B 
muammolari kirish va o'zgartirilgan kirish uchun bir xil javobni (Ha yoki Yo'q) 
berishi kerak. A dan B gacha qisqartirish algoritmining mavjudligi quyidagilarni 
nazarda tutadi: 
1. Agar B ∈ P bo'lsa, u holda A ∈ P (ko'paytmali vaqt ichida A dan B gacha 
qisqartirishingiz mumkin va B polinomik vaqt ichida echishingiz mumkin. Buni 
birlashtirish A uchun ko'p vaqtli algoritmni beradi) 
2. Agar B ∈ NP bo'lsa, unda A ∈ NP 
3. Agar A NP-qattiq bo'lsa, B - NP-qattiq. A ko'paytirilgan vaqt ichida B ga kamayishi 
mumkin va agar B NP-qiyin bo'lmasa, u B B NP-NP-qiyin va bu A ∈ NP-NP-qattiq, bu 
farazga zid (A-NP-qiyin) degan ma'noni anglatadi. 

---

• 
NP-to'liqligi - agar X ∈ NP va X bo'lsa, NP-qiyin bo'lsa, X muammo NP-
tugallanadi. 
Muammo NP-tugaganligini isbotlash 
Muammoning to'liqligini isbotlash 2 bosqichni o'z ichiga oladi. Avval biz muammo NPga 
tegishli ekanligini ko'rsatishimiz kerak va keyin biz buni NP-qiyinligini ko'rsatishimiz 
kerak. Bosqichlarni quyidagicha izohlash mumkin: 
1-qadam - X ∈ NP ni ko'rsatish. X uchun netereterministik algoritmni toping. Ammo amaliy 
usul, agar potentsial echim taqdim etilsa, X uchun ko'paytmali vaqt tekshiruvini 
o'tkazishdir. 
2-qadam - X-ni ko'rsatish qiyin emas. Ma'lum NP-muammoni X-ga qisqartirish. Demak, 
biz 
ko'rgan 
3-rasm 
orqali 
X 
bu 
NP-qiyin 
ekanligini 
anglatadi. 
Bu 
masala 
qisqa 
P 
va 
NP 
murakkab 
sinfi 
tengmi? 
P-sinfi deb kompyuter “tezda”(“Birzumda”) yechimi mumkin bo’lgan masalalar majmuiga 
aytiladi. Bunga arifmetik amallarning asosi (negizi) ro’yhatlarni saralash, jadval bo’yicha 
ma’lumotlarni 
izlash 
kiradi. 
NP-sinfiga javobning to’g’riligini tezda tekshirish mumkin bo’lgan masala kiradi. Masalan: 
faraz qilaylik sizda qiymati 2,3,5,6 va 7 so’mlik tangalardan bittadan bor va siz narxi 21 
so’m bo’lgan harid uchun qaytimsiz to’lashni hoxlamoqdasiz. Ulardan yig’indisi 21 so’m 
bo’lgan 
tangalarni 
yig’ib 
olish 
mumkinmi? 
Bu masalaga javob olish uchun har hil variantni tanlash lozim, agar masala yechimini 
yo’qligini isbotlasmoqchi bo’lsak, umuman olganda barcha bo’lishi mumkin bo’lgan 
variantlardni tanlash lozim. Agar tangalar sonini bir necha usulda ko’paytirsak yechish 
mutlaqo nomuvofiq ko’rinishda bo’ladi. Bunda natijani oson tekshirish uchun shunchaki 
barcha “ming yillik masalasi” ning mohiyati quyidagicha (bunday) ifodalanadi 
(ta’riflanadi): P va NP sinflari tengmi? Agar masala yecvhimining to’g’riligini tekshirish 
oson 
bo’lsa, 
masalani 
o’zini 
yechish 
ham 
oson 
bo’lishi 
mumkinmi? 
Ko’pchilik mutaxassislar javobning yo’qligi (salbiy)ga amindirlar, lekin buni hozircha hech 
kim isbotlay olgani yo’q agar P=NP bo’lib qolsa, unda insoniyatni kriptografiyaga (sirli 
belgi va ishoralar bilan yozish tizimi) keskin burilish ko’taradi.