Muhammad al-xorazimiy nomidagi toshkent axborot texnologiyalari universiteti

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