Algoritmning murakkablik sinflari p masalalar sinfi np masalalar sinfi

13-ma’ruza.
Mavzu: NP- to’liq masalalar. Hisoblashda yechilmaslik hollari
Reja

1. 
   Algoritmning murakkablik sinflari
   
2. 
   P masalalar sinfi
   
3. 
   NP masalalar sinfi
   
4. 
   NP- to’liq masalalar sinfi
   

Kalit so’zlar: polynomial, eksponensial, superpolinomial, P masalalar, NP masalalar,
Algortmlar murakkabligini baxolash uchun O-simvolika dan foydalaniladi.
Ushbu baxolash asosida algoritmlarni kuyidagi sinflarga bulish mumkin (kiruvchi ma’lumotla n ga teng bulganda) :

• 
  Doimiy – murakkablik n ga boglik emas: O(1);
  
• 
  Chizikli – murakkablik: O(n);
  
• 
  polinomial – murakkablik: O(n^m), bu yerda m - konstanta;
  
• 
  eksponensial – murakkablik: O(t^f(n)), bu yerda t – konstanta > 1, f(n) – polinomial funksiya;
  
• 
  superpolinomial – murakkablik: O(s^f(n)), bu yerda s – konstanta, f(n) – doimiydan tezrok lekin chiziklidan sekinrok usadigan funksiya. Oddiy masalalar (yechib buladigan) –polinomial vaktda yechish mumkin bulan masalalar.
  

Kiyin yechiladigan masalalar– bu masalalar polinomial vaktda yechilmaydi yoki polinomial vaktda yechish algoritmi topilmaydi.
Sinflarga ajratish
1. P-masalalar (polinomial masalalar) - polinomial vaktda yechish mumkin bulgan masalalar.
2. NP-masalalar (determinirlanmagan polinomial masalalar) fakatgina determinirlanmagan Tyuring mashinasida yechish mumkin bulgan masala. Bu masalalarning javoblari mavjud, ularni topish kiyin lekin polinomial vaktda tekshirish mumkin.
3. NP-tulik masalalar deb, unga NP sinfidan boshqa har qanday masalani polinom vaqtida kamaytirish mumkin. Shunday kilib, tulik masalalar kandaydir ma’noda NP sinfidagi «eng kiyin» masalalar kism tuplamini ifodalaydi.
Agar ularning birontasini yechishning «tez» algoritmi topilsa, u xolda NP sinfdagi ixtiyoriy masala xam shunday «tez» yechish mumkin.
Ixtiyoriy NP – tulik masalani polinomial vaktda yechish algoritmi topilsa NP – masalani xam polinomial vaktda yechish mumkin buladi, ya’ni ularni R-masala deb xisoblash mumkin buladi.
4. EXPTIME sinfi–eksponensial vaktda yechiladigan masalalar sinfi.
5. EXPTIME-tulik masalalar sinfi–determinirlangan polinomial vaktda yechilmaydigan masalalar sinfi.
NP-tulik masalalarga misol

• 
  Kommivoyajyor masalasi
  

Grafni buyash masalasi va x.k.