Texnalogiyalari universiteti 030-20 guruh talabasi Xayridinov Vohidjonning

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 
 

---

Foydalanilgan 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 
c.
https://uz.wikipedia.org/