O‘zbekiston Respublikasi axborot texnologiyalari va kommunikatsiyalarni rivojlantirish vazirligi

NP-to‘liqlik masalasining kuchlilik tomoni 
Agar masalaning qisim masalalari mavjud bo‘lsa u kuchli NP-to‘liq masala deyiladi, 
bunda: Masalaning raqamli parametrlari mavjud bo‘lmasa (ya'ni, bu masalada 
uchraydigan kattaliklarning maksimal' qiymati polinom uzunligi bilan yuqoridan 
chegaralangan). 
Masalaning raqamli parametrlari mavjud bo‘lmasa (ya'ni, bu masalada 
uchraydigan kattaliklarning maksimal' qiymati polinom uzunligi bilan yuqoridan 
chegaralangan). 
NP-to‘liqlik masala. 
Bunday vazifalar sinfi NPCS deb nomlanadi. Agar P ≠ NP gipotezasi to‘g‘ri bo‘lsa, 
unda NPCS masalasi uchun soxtaopolinomial algoritm mavjud emas. 
NP-to‘liqlik masalaga misollar 
Bul' formulalari bajarilishi masalasi
"Dog‘lar" n × n o‘lchamining eng qisqa yechimi
Kommivoyajyora masalasi 
Shteyner muammosi 
Grafani bo‘yash masalasi 
Soxa (yuza) qoplamasi masalasi
To‘plamni qoplash masalasi
Tanlash masalasi
To‘plamning mustaqilligi masalasi
Saper (o‘yin) 
Tetris 

---

Adabiyotlar 
1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые 
задачи. М.: Мир, 1982. 
2. Томас Х. Кормен и др. Боб. 34 NP-полнота // Алгоритмы: построение и 
анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. 
— 1296 с. — ISBN 0-07-013151-1. 
3. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в 
теорию автоматов, языков и вычислений = Introduction to Automata 
Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — 
ISBN 0-201-44124-1. 
4. Internet saytlari: 
a) https://en.wikipedia.org/wiki/P_versus_NP_problem 
b) http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2025%
20-%20P%20and%20NP.htm 
https://uz.wikipedia.org/ 
https://fayllar.org