Mavzu: n-to’liq masalalarni yechish algoritmlarini qiyinligini baxolash

Masalalarning sinflar bo’yicha murakkabligi

• 
  Ushbu ikkita xususiyatga asoslanib, ko’pchilik P ≠ NP taxminini ilgari surishadi. NP-to'liq masalalar kontseptsiyasining amaliy ma'nosi, aynan shu kabi masalalarni hal qilish qiyin bo'lgan masalalar degan keng tarqalgan fikrni ilgari suradi. Binobarin, ularni eng yomon holatda hal qilish eksponensial vaqtni talab qiladi va juda oz sonli individual muammolardan tashqari, bunday muammolarni amalda hal qilish mumkin bo'lmaydi.
  

Masalalarning sinflar bo’yicha murakkabligi

• 
  2) NP klassi (polinom bo'yicha Tyuring mashinasida tekshiriladigan muammolar)
  
• 
  Tasavvur qiling, qandaydir algoritm qandaydir muammoga yechim topadi - javob berilgan vazifaga to'g'ri keladimi va biz uning to'g'riligini qanchalik tez tekshira olamiz?
  
• 
  Masalan, summa muammosini ko'rib chiqing:
  
• 
  • V raqam va N ta raqam berilgan - A = (a1, ... an).
  
• 
  • Muammo: X = (,…, ), ∈ {0,1} vektorni (massiv) toping, shunda ∑ = V.
  
• 
  • Mazmunan: V sonini A massivning istalgan elementlari yig'indisi sifatida ko'rsatish mumkinmi?
  

• 
  

NP sinfiga misollar

• 
  Mantiqiy shaklda bajarilish masalasi (SAT)
  
• 
  Grafda Gamilton sikli mavjudligini aniqlash
  
• 
  Kommivoyajer haqida masala
  
• 
  Grafning tugunli qoplamasini topish masalasi
  

Gamilton yo’li / sikli

• 
  Gamiltonian yo'li - grafadagi har bir tugunni to'liq bir marta o'z ichiga olgan grafdagi yo'l
  
• 
  Gemilton sikli - bu Gamilton yo'lidir, uning boshlang'ich va oxirgi tugunlari bir-biriga to'g'ri keladi
  

Gamilton yo’li / sikli

Kommivoyajer masalasi

• 
  Kommivoyajer masalasi (ing. Travelling salesman problem, TSP)