?

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}))$

sat exp-time-algorithms nexp

— Igor Shinkar
źródło

Odpowiedzi:

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.

— Manu
źródło

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

— Huck Bennett
źródło

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.