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

Kvazi-polinom vaqt

Algoritmlar kvazi-polinom vaqt polinom vaqtidan sekinroq ishlaydigan, lekin eksponent vaqt algoritmlari kabi sekin boʻlmagan algoritmlardir. Kvazi polinomial algoritm uchun eng yomon ish vaqti v... Butun sonni omillarga ajratish boʻyicha taniqli klassik algoritm, emas kvazi-polinom hisoblanadi, chunki ish vaqti quyidagicha ifodalanmaydi 2 O ((log-n) c) (\\ displaystyle 2 ^ (O ((\\ log n) ^ (c)))) baʻzilari uchun sobit v... Agar kvazi-polinom vaqt algoritmining taʻrifida doimiy "c" 1 boʻlsa, biz koʻp polinom vaqt algoritmini olamiz, va agar u 1 dan kam boʻlsa, sublinear vaqt algoritmini olamiz.vazi-polinom vaqt algoritmlari odatda NP qattiq muammoni boshqa muammoga kamaytirishda paydo boʻladi. Masalan, siz NP-ga oʻxshash muammoni, masalan, 3SATni qabul qilishingiz va uni boshqa B muammosiga kamaytirishingiz mumkin, ammo muammoning kattaligi 2 O ((log-n) c) (\\ displaystyle 2 ^ (O ((\\ log n) ^ (c))))... Bunday holda, qisqartirish B muammoning NP-qattiq ekanligini isbotlamaydi; bunday qisqartirish faqat B uchun polinom algoritmi mavjud emasligini koʻrsatadi, agar 3SAT uchun kvazi-polinom algoritmi boʻlmasa (va keyin barcha-muammolar uchun). Xuddi shunday - biz kvaz polinomial vaqt bilan algoritmlarni biladigan, ammo polinom vaqt bilan algoritmlarni nomaʻlum boʻlgan baʻzi muammolar mavjud. Bunday muammolar taxminiy algoritmlarda paydo boʻladi. Mashhur misol - yaqinlashtirilgan koeffitsientli kvazi-polinomli yaqinlashtirish algoritmi mavjud boʻlgan yoʻnaltirilgan Shtayner muammosi. O (log 3-n) (\\ displaystyle O (\\ log ^ (3) n))) (bu erda n - tepalar soni), lekin koʻp polinomli vaqt algoritmining mavjudligi ochiq muammo.

Qiyinchilik darsi QP kvazi polinomial vaqt algoritmlari bilan bogʻliq barcha muammolardan iborat. Uni DTIME nuqtai nazaridan quyidagicha aniqlash mumkin.

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