Mavzu: p va np sinflari. Np to’liq masala tushunchasi

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). 
Mas
alaning 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: 
.
https://en.wikipedia.org/wiki/P_versus_NP_problem 
a.
http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2025%20-
%20P%20and%20NP.htm 
b.
https://uz.wikipedia.org/ 

---