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

Masalalarning sinflar bo’yicha murakkabligi

• 
  Ushbu sinf algoritmlarining quyidagi afzalliklari e'tiborga loyiq:
  
• 
  • P sinfidagi ko'pgina muammolar uchun k doimiysi 6 dan kam;
  
• 
  • hisoblash modeli bo'yicha P klassi o'zgarmasdir (keng modellar sinfi uchun);
  
• 
  • P klassi tabiiy ravishda yopiq (ko'pburchaklarning yig'indisi yoki ko'paytmasi ko'pburchakdir).
  
• 
  • Shunday qilib, P sinfidagi masalalar "amalda yechiladigan" muammoning ta'rifini takomillashtirishdir.
  

Eslatma: Agar algoritm T(n)ÎO(n) bo’lsa chiziqli ishlash vaqtiga ega deyiladi, T(n)ÎO(na) algoritm a>1 bo’lganda polynomial ishlash vaqtiga ega deyiladi. Algoritm eksponensial ishlash vaqtiga ega deyiladi, agar T(n) yuqoridan 2poly(n) qiymati bilan chegaralangan bo’lsa, bunda poly(n) - n dan qandaydir polinom. Rasman aytganda, algoritm eksponensial vaqt bilan ishlaydi deb agar T(n) k qandaydir konstanta uchun O() bilan chegaralansa.

P sinfiga misollar

• 
  Raqamlar yig'indisini hisoblash
  
• 
  Raqamlarning ko'paytmasini hisoblash
  
• 
  Raqamni tublikka tekshirish
  
• 
  Massivni saralash
  
• 
  Grafning bog’lanishini aniqlash
  
• 
  Eyler yo'li / sikli
  

Masalalarning sinflar bo’yicha murakkabligi

• 
  NP sinfida NP-to'liq masalalar ajratiladi. Agar masala NPda yuzaga kelsa va NPdagi har bir masala unga polinomial ravishda kamaytirib borilsa (ya'ni NP-qattiq) bo'lsa, NP-to'liq deb nomlanadi. NP-to'liq masalalar NP sinfidagi eng qiyin masalalar sifatida tushuniladi. NP-to'liq masalalar klassi quyidagi xususiyatlarga ega.
  
• 
  (1) Ko'plab ajoyib tadqiqotchilarning qat'iyatli harakatlariga qaramay, biron bir ma'lum bo'lgan polinom algoritmi bilan biron bir NP bilan yakunlangan muammoni hal qilish mumkin emas.
  
• 
  (2) Agar biron bir NP bilan yakunlangan muammo uchun polinom algoritmini tuzish mumkin bo'lsa, demak bu har bir NP-to'liq masalaning polinom yechimliligini anglatadi.