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

Super polinom vaqti

Algoritm uchun ishlaydi deyiladi superpolinom vaqt, agar a T(n) yuqorida koʻpburchak bilan chegaralanmagan. Bu vaqt ω ga teng ( n v) barcha doimiylar uchun vqayerda n kirish parametri, odatda kirish bitlari soni.

Masalan, 2-ni amalga oshiruvchi algoritm n hajmini kiritish uchun qadamlar n superpolinomiya vaqtini (aniqrogʻi, eksponent vaqtni) talab qiladi.

Koʻrsatkichli manbalardan foydalanadigan algoritm superpolinomial ekanligi aniq, ammo baʻzi algoritmlar juda zaif superpolinomialdir. Masalan; misol uchun, adleman - Pomeranza - Roumeli soddaligi testi * oʻz vaqtida ishlaydi n O (jurnal jurnali n) ustida n-bit kirish. U etarlicha katta boʻlish uchun har qanday polinomdan tezroq oʻsadi n, lekin kirish hajmi juda katta boʻlishi kerak, shunda u kichik polinom tomonidan ustun boʻlmaydi.

Superpolinomial vaqtni talab qiladigan algoritm murakkablik sinfidan tashqarida. Kobxemning tezisi ushbu algoritmlarning amaliy emasligini taʻkidlaydi va koʻp hollarda ular shundaydir. P va NP sinflarining tengligi muammosi hal qilinmaganligi sababli, hozirda polinom vaqtidagi NP toʻliq masalalarni echish algoritmlari maʻlum emas.