Algoritmning vaqt murakkabligini baholash. Algoritmlar murakkabligi funksiyalarining turlari Doimiy vaqt

Algoritm murakkabligi sinflari
Aniq qiyinchilik sinflari: Bular xuddi shunday qiyinchilikka ega toifalar.
Quyidagi asosiy qiyinchilik sinflari ajratiladi:
DTIME Tyuring mashinasi muammoning yechimini cheklangan vaqt ichida (qadamlar soni) topadi. Algoritmning asimptotikasi ko'pincha belgilanadi, shuning uchun aytaylik, agar ish vaqtining o'sish tartibi \ (T (n) = \ mathcal (O) (f (n)) \), keyin \ (DTIME (f) bo'lsa. (n)) \) ko'rsatilgan. P Turing mashinasi muammoning yechimini polinom vaqtida (qadamlar soni) topadi, ya'ni. \ (T (n) = \ matematik (O) (n ^ k) \), bu erda \ (k \ in \ mathbb (N) \). \ (P = DTIME (n ^ k) \) EXPTIME Tyuring mashinasi muammoning yechimini eksponensial vaqtda (qadamlar soni) topadi, ya'ni. \ (T (n) = \ matematik (O) (2 ^ (n ^ k)) \), bu erda \ (k \ in \ mathbb (N) \). \ (EXPTIME = DTIME (2 ^ (n ^ k)) \). DSPACE Turing mashinasi cheklangan miqdordagi qo'shimcha xotira (hujayralar) yordamida muammoning yechimini topadi. Algoritmning asimptotikasi ko'pincha belgilanadi, shuning uchun aytaylik, agar xotira iste'molining o'sish tartibi \ (S (n) = \ mathcal (O) (f (n)) \), keyin \ (DSPACE (f ()) n)) \) ko'rsatilgan. L Tyuring mashinasi logarifmik fazoviy murakkablikdagi muammoning yechimini topadi, ya'ni. \ (S (n) = \ matematik (O) (\ log n) \)... \ (L = DSPACE (\ log n) \). PSPACE Tyuring mashinasi polinom fazoviy murakkablikdagi masalaning yechimini topadi, ya'ni \ (S (n) = \ mathcal (O) (n ^ k) \), bu erda \ (k \ in \ mathbb (N) \ ). \ (PSPACE = DSPACE (n ^ k) \). EXPSPACE Turing mashinasi eksponensial fazoviy murakkablikdagi muammoning yechimini topadi, ya'ni. \ (S (n) = \ matematik (O) (2 ^ (n ^ k)) \), bu erda \ (k \ in \ mathbb (N) \). \ (EXPSPACE = DSPACE (2 ^ (n ^ k)) \).
Bundan tashqari, kontseptsiyada ishlaydigan nazariy murakkablik sinflari mavjud aniqlanmagan Tyuring mashinalari (TMT). Ularning ta'riflari yuqoridagilarga to'g'ri keladi, Tyuring mashinasini NMT bilan almashtirish va nomlar N prefiksiga ega (masalan, NP), NTIME va NSPACE bundan mustasno, bu erda D N bilan almashtiriladi.
NMT - bu sof nazariy konstruktsiya bo'lib, u o'zining ishlash tamoyillari bo'yicha MTga o'xshaydi, farqi bilan har bir shtat uchun mavjud bo'lishi mumkin. bir nechta mumkin bo'lgan harakatlar. Shu bilan birga, NMT har doim mumkin bo'lgan harakatlardan minimal mumkin bo'lgan qadamlar sonida yechimga olib keladiganini tanlaydi. Xuddi shunday, HMT hisoblaydi hammasidan novdalar va minimal mumkin bo'lgan qadamlar sonida yechimga olib keladigan filialni tanlaydi.
Ba'zida kvant kompyuterlari HMT ning qo'llanilishi deb eshitiladi. Ba'zi hollarda bu to'g'ri ko'rinishi mumkin bo'lsa-da, umuman olganda, HMT kvant kompyuteriga qaraganda kuchliroq tizimdir.
Ma'lumki \ (P \ subseteq NP \ subseteq PSPACE \ subseteq EXPTIME \ subseteq NEXPTIME \ subseteq EXPSPACE \)
Shuningdek, \ (P \ subsetneq EXPTIME \), \ (NP \ subsetneq NEXPTIME \), \ (PSPACE \ subsetneq EXPSPACE \)
Bundan tashqari, ma'lumki, agar \ (P = NP \), keyin \ (EXPTIME = NEXPTIME \).
P va NP tengligi masalasi zamonaviy kompyuter fanining hal qilinmagan asosiy savollaridan biridir.