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

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.