«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan Mustaqil ish

Toʻliq muammolar bilan bogʻlanish

Murakkablik nazariyasida, P va NP sinflari oʻrtasidagi echilmagan tenglik muammosi, NP sinfidagi barcha masalalarda polinom vaqtida echish algoritmlari mavjudligini soʻraydi. 3SAT kabi NP-toʻliq muammolari uchun barcha taniqli algoritmlar eksponent vaqtga ega. Bundan tashqari, koʻplab tabiiy NP-ning toʻliq muammolari uchun subekspentsial bajarish vaqtiga ega algoritmlar mavjud emas degan gipoteza mavjud. Bu erda "subeksponent vaqt" quyida keltirilgan ikkinchi taʻrif maʻnosida olinadi. (Boshqa tomondan, qoʻshni matritsalar bilan ifodalangan tabiiy ravishda koʻplab grafika nazariyasi muammolari subponponentsial vaqtda echimini topadi, chunki kirish kattaligi tepalar sonining kvadratiga tengdir.) Bu gipoteza (k-SAT muammosi uchun ) nomi bilan tanilgan eksponent vaqt haqidagi gipoteza ... NP-toʻliq masalalarda kvazi-polinom vaqt algoritmlari mavjud emas deb taxmin qilganligi sababli, yaqinlashuv algoritmlari sohasidagi yaqinlashmaslikning baʻzi natijalari NP-toʻliq masalalarda kvazi-polinom vaqt algoritmlari mavjud emas deb taxmin qiladi. Masalan, toʻsiq qoplamasi muammosining yaqinlashmasligi haqidagi taniqli natijalarga qarang.