Mavzu: Algoritm murakabligini statik va dinamik o’lchovlari. Vaqt va xotira xajmi bo’yicha qiyinchiliklar

NP-to'liq muammolar bilan munosabatlar
Murakkablik 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.
Subeksponensial vaqt
Muddati subeksponensial vaqt ba'zi algoritmlarning bajarilish vaqti har qanday ko'phadga qaraganda tezroq o'sishi mumkinligini ifodalash uchun ishlatiladi, lekin u eksponensialdan sezilarli darajada kamroq bo'lib qoladi. Shu ma'noda, subeksponensial vaqt algoritmlari bilan bog'liq muammolar faqat eksponensial vaqtli algoritmlarga qaraganda ancha moslashuvchan. "Sub-eksponensial" ning aniq ta'rifi hali umumiy qabul qilinmagan va biz quyida eng keng tarqalgan ikkita ta'rifni keltiramiz.
Birinchi ta'rif
Agar muammo ish vaqtining logarifmi har qanday berilgan ko‘phaddan kamroq o‘sadigan algoritm bilan yechilsa, muammo subeksponensial vaqtda yechilgan deyiladi. Aniqroq qilib aytadigan bo'lsak, har qanday e> 0 uchun muammoni O (2 n e) vaqtida hal qiluvchi algoritm mavjud bo'lsa, masala subeksponensial vaqtga ega bo'ladi. Bunday masalalarning barchasi murakkablik sinfini tashkil qiladi SUBEXP, bu DTIME jihatidan ifodalanishi mumkin.
SUBEXP = ⋂ e> 0 DTIME (2 n e) (\ displaystyle (\ text (SUBEXP)) = \ bigcap _ (\ varepsilon> 0) (\ text (DTIME)) \ chap (2 ^ (n ^ (\ varepsilon) ))) \ to'g'ri))
E'tibor bering, bu erda e kiritilgan ma'lumotlarning bir qismi emas va har bir e uchun muammoni hal qilishning o'ziga xos algoritmi bo'lishi mumkin.