1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi 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.