Mavzu : Algoritm murakkabligini statik va dinamik o’lchovlari. Vaqt va xotira hajmi bo’yicha qiyinchiliklar reja

Qiyinchilik sinflari
Polinom vaqt tushunchasi hisoblash murakkabligi nazariyasida bir necha murakkablik sinflariga olib keladi. Polinom vaqti yordamida aniqlangan ba'zi muhim sinflar quyida ko'rsatilgan.

• 
  : Polinom vaqtida deterministik Tyuring mashinasida echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi.
  
• 
  : Polinom vaqtida deterministik bo'lmagan Tyuring mashinasida echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi.
  
• 
  ZPP: Polinom vaqtida ehtimolli Tyuring mashinasida nol xato bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi.
  
• 
  : Polinom vaqtida ehtimolli Tyuring mashinasida bir tomonlama xatolar bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik klassi.
  
• 
  BPP polinom vaqtidagi ehtimollik Tyuring mashinasi.
  
• 
  BQP: Polinom vaqtida kvant Tyuring mashinasida ikki tomonlama xatolar bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik klassi.
  

P - deterministik mashinadagi eng kichik vaqt murakkabligi sinfi, ya'ni barqaror mashina modelini o'zgartirish nuqtai nazaridan. (Masalan, bitta lentali Tyuring mashinasidan ko'p tarmoqli Tyuring mashinasiga o'tish kvadratik tezlikka olib kelishi mumkin, lekin bir modelda polinom vaqtida ishlaydigan har qanday algoritm boshqasida polinom vaqtida ishlaydi.)
Super polinom vaqti
Algoritm ishlashi aytiladi superpolinom vaqti, agar T(n) yuqorida ko‘phad bilan chegaralanmagan. Bu vaqt ō ga teng ( n c) barcha konstantalar uchun c, qayerda n kirish parametri, odatda kirish bitlari soni.
Masalan, 2 ni amalga oshiradigan algoritm n hajmini kiritish uchun qadamlar n superpolinom vaqtni talab qiladi (aniqrog'i, eksponensial vaqt).
Ko'rsatkichli resurslardan foydalanadigan algoritm superpolinom ekanligi aniq, lekin ba'zi algoritmlar juda zaif superpolinomdir. Masalan, Adleman-Pomeranza-Roumeli soddaligi testi * vaqt uchun ishlaydi n O (jurnal jurnali n) ustida n-bit kiritish. U etarlicha katta bo'lgan har qanday polinomdan tezroq o'sadi n, lekin kirishning o'lchami juda katta bo'lishi kerak, shuning uchun u kichik darajadagi polinom tomonidan hukmronlik qilmasligi kerak.
Superpolinom vaqt talab qiladigan algoritm murakkablik sinfidan tashqarida. Kobhamning tezislari bu algoritmlar amaliy emas, deb da'vo qiladi va ko'p hollarda ular. P va NP sinflarining tengligi masalasi hal etilmaganligi sababli, hozirgi vaqtda NP-to'liq masalalarni polinom vaqtida yechish algoritmlari ma'lum emas.