Domov > Obvestila > David Gajser: co-NP-polni problemi, ki jih ni moč rešiti v času O(n^c), za nek v naprej izbran c

David Gajser: co-NP-polni problemi, ki jih ni moč rešiti v času O(n^c), za nek v naprej izbran c

Datum objave: 12. 5. 2014
Vir: Seminar za teorijo grafov in algoritme
Četrtek 15. 5. 2014 ob 12:15 v PS na Jadranski 19

Naj bo $RUN_{C,D}$ naslednji odločitveni problem (naravni števili $C$ in $D$ sta parametra):
  Vhod: 1-tračni Turingov stroj $M$
  Vprašanje: Ali $M$ na vseh vhodih dolžine $m$, za vsak $m$, naredi največ $Cm+D$ korakov?

Najprej opazimo, da ni očitno niti, ali je to sploh odločljiv (algoritmično rešljiv) problem ali ne. Izkaže se, da je in da obstaja nedeterministični Turingov stroj, ki reši komplement tega problema v času $O(n^{C/2+1})$. Zares pa so zanimiva naslednja dejstva, ki veljajo za $C\geq 2$ in $D\geq 1$:

  • $RUN_{C,D}$ je co-NP-poln problem,
  • $RUN_{C,D}$ ne gre rešiti z nedeterminističnim Turingovim strojem v času $o(n^{(C-1)/8})$, 
  • komplement $RUN_{C,D}$ ne gre rešiti z nedeterminističnim Turingovim strojem v času $o(n^{(C-1)/4})$.

Gre za unikaten primer problema s temi dokazljivimi lastnostmi (glede na avtorjevo poznavanje področja). Še najlepše pa je, da je problem (relativno) naraven.