?

Czy to możliwe, że ? Czy są interesujące konsekwencje takiego ograniczenia? Czy byłoby to sprzeczne z hipotezą o wykładniczym czasie?$\overline{SAT} \in NTIME(\exp(n^{0.9}))$

To jest możliwe ;-)

Dałoby to nowym obwodom dolne granice. Ponieważ przyjmujesz dość mocne założenie, może to wynikać z przełomowej pracy Impagliazza, Kabanetsa i Wigdersona. Nie sprawdziłem.

$n^{1+\Omega(1)}$$n$$^{NP}$$s$$O(s)$$O(s)$ zmienne według Cook-Levin.

Nie byłoby to sprzeczne bezpośrednio z ETH, ponieważ dotyczy to algorytmów deterministycznych.

$\text{NTIME}[2^{(1-\varepsilon) n}]$