Np-to‘liklik masalasi

NP-to‘liklik 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).

1. 
   Masalaning raqamli parametrlari mavjud bo‘lmasa (ya’ni, bu masalada uchraydigan kattaliklarning maksimal qiymati polinom uzunligi bilan yuqoridan chegaralangan).
   
2. 
   NP-to‘liklik 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‘liklik 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. 
   Geri M., Djonson D. Vыchislitelnыe mashinы i trudnoreshayemыe zadachi. M.: Mir, 1982.
   
2. 
   Tomas X. Kormen i dr. Bob. 34 NP-polnota // Algoritmы: postroyeniye i analiz = Introduction to Algorithms. — 2-e izd. — M.: «Vilyams», 2006. — 1296 s. — ISBN 0-07-013151-1.
   
3. 
   Djon Xopkroft, Radjiv Motvani, Djeffri Ulman. Vvedeniye v teoriyu avtomatov, yazыkov i vыchisleniy = Introduction to Automata Theory, Languages, and Computation. — M.: «Vilyams», 2002. — 528 s. — ISBN 0-201-44124-1.