Toshkent axborot texnologiyalari universiteti mustaqil ish mavzu: Algoritm murakkabligini statik va dinamik o'lchovlari. Vaqt va xotira hajmi bo'yicha qiyinchiliklar

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.)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.Algoritmlar kvazi-polinomli vaqt Bu algoritmlar polinom vaqtidan sekinroq ishlaydi, lekin eksponensial vaqt algoritmlari kabi sekin emas. Kvazi-polinomli algoritm uchun eng yomon ish vaqti c... Butun sonni omillarga ajratish uchun taniqli klassik algoritm, emas kvazi-polinom hisoblanadi, chunki ish vaqtini quyidagicha ifodalab bo'lmaydi 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c)))) ba'zilari uchun sobit c... Kvazipolinomli vaqt algoritmi ta'rifidagi doimiy "c" 1 ga teng bo'lsa, ko'p nomli vaqt algoritmini, 1 dan kichik bo'lsa, pastki chiziqli vaqt algoritmini olamiz.Kvazi-polinomli vaqt algoritmlari odatda NP-qiyin muammoni boshqa masalaga qisqartirganda paydo bo'ladi. Xuddi shunday, ba'zi muammolar mavjud bo'lib, ular uchun biz kvazi-polinomli vaqtli algoritmlarni bilamiz, lekin ular uchun ko'p nomli vaqtli algoritmlar noma'lum. Bunday muammolar taxminiy algoritmlarda paydo bo'ladiMurakkablik nazariyasida P va NP sinflari orasidagi tenglikning yechilmagan muammosi NP sinfidagi barcha masalalarni polinom vaqtida yechish algoritmlari borligini so'raydi. 3SAT kabi NP-to'liq muammolar uchun barcha taniqli algoritmlar eksponensial vaqtga ega. Bundan tashqari, ko'pgina tabiiy NP-to'liq muammolar uchun subeksponensial bajarish vaqti bilan algoritmlar mavjud emas degan gipoteza mavjud. Bu yerda “subeksponensial vaqt” quyidagi ikkinchi taʼrif maʼnosida olingan. (Boshqa tomondan, tabiiy ravishda qo'shni matritsalar bilan ifodalangan ko'plab grafik nazariyasi muammolari subeksponensial vaqtda echilishi mumkin, chunki kirishning o'lchami cho'qqilar sonining kvadratiga tengdir.) Bu gipoteza (k-SAT muammosi uchun) sifatida tanilgan eksponensial vaqt gipotezasi... NP-to'liq masalalarda kvazi-polinomli vaqt algoritmlari mavjud emas deb taxmin qilinganligi sababli, ba'zi bir yaqinlashmaslik natijalari yaqinlashish algoritmlari sohasiga olib keladi, NP-to'liq masalalarda kvazi-polinomli vaqt algoritmlari mavjud emas deb taxmin qilinadi. Misol uchun, to'plamni qoplash muammosining yaqinlashmasligi haqidagi taniqli natijalarga qarang.Muddati