1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar

Kvazi-polinomli vaqt

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. Masalan, siz NP uchun qiyin masalani qabul qilishingiz mumkin, masalan, 3SAT va uni boshqa B muammosiga qisqartirishingiz mumkin, ammo muammoning hajmi kattalashadi. 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c))))... Bunday holda, qisqartirish B muammosi NP-qiyin ekanligini isbotlamaydi; bunday qisqartirish faqat B uchun polinom algoritmi yo'qligini ko'rsatadi, agar 3SAT uchun kvazipolinomli algoritm mavjud bo'lmasa (va keyin barcha muammolar uchun). 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'ladi. Mashhur misol - Shtaynerning yo'naltirilgan muammosi bo'lib, u uchun yaqinlashish koeffitsientiga ega bo'lgan taxminiy kvazi-polinom algoritmi mavjud. O (log 3 ⁡ n) (\ displaystyle O (\ log ^ (3) n))(bu erda n - cho'qqilar soni), lekin ko'p nomli vaqt algoritmining mavjudligi ochiq muammodir.

Qiyinchilik klassi QP kvazi-polinomli vaqt algoritmlari bilan bog'liq barcha masalalardan iborat. Uni DTIME nuqtai nazaridan quyidagicha aniqlash mumkin

QP = ⋃ c ∈ N DTIME (2 (log ⁡ n) c) (\ displaystyle (\ mbox (QP)) = \ bigcup _ (c \ in \ mathbb (N)) (\ mbox (DTIME)) (2 ^ ((\ log n) ^ (c))))