«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan Mustaqil ish

Qiyinchilik darslari

Polinom vaqt tushunchasi hisoblash murakkabligi nazariyasida bir necha murakkablik sinflariga olib keladi. Polinom vaqtidan foydalanib aniqlangan baʻzi muhim sinflar quyida koʻrsatilgan.

• 
  : Polinom vaqtidagi deterministik Turing mashinasida echilishi mumkin boʻlgan echuvchanlik masalalarining murakkabligi klassi.
  
• 
  : Polinom vaqtida determinatsiyalanmagan Tyuring mashinasida echilishi mumkin boʻlgan echuvchanlik masalalarining murakkablik sinfi.
  
• 
  ZPP: Polinom vaqtidagi ehtimoliy Turing mashinasida nol xato bilan echilishi mumkin boʻlgan echuvchanlik masalalarining murakkabligi klassi.
  
• 
  : Polinom vaqtidagi ehtimoliy Turing mashinasida bir tomonlama xatolar bilan echilishi mumkin boʻlgan echuvchanlik masalalarining murakkabligi sinfi.
  
• 
  BPP polinom vaqtidagi ehtimoliy Turing mashinasi.
  

BQP: Polinom vaqtidagi kvant Tyuring mashinasida ikki tomonlama xatolar bilan echilishi mumkin boʻlgan echuvchanlik masalalarining murakkablik sinfi.

P - bu deterministik mashinadagi eng kichik vaqt murakkabligi sinfi barqaror mashina modelini oʻzgartirish nuqtai nazaridan. (Masalan, bitta lentali Turing mashinasidan koʻp lentali Turing mashinasiga oʻtish kvadratik tezlikni keltirib chiqarishi mumkin, ammo bir modelda polinom vaqtida ishlaydigan har qanday algoritm boshqasida polinom vaqtida ishlaydi.)