?

Est-il possible que ? Y a-t-il des conséquences intéressantes d'un tel confinement? Cela contredirait-il l'hypothèse du temps exponentiel?$\overline{SAT} \in NTIME(\exp(n^{0.9}))$

C'est possible ;-)

Cela donnerait au nouveau circuit des limites inférieures. Puisque vous faites une hypothèse assez forte, cela pourrait découler du travail fondateur d'Impagliazzo, Kabanets et Wigderson , je n'ai pas vérifié.

$n^{1+\Omega(1)}$$n$$^{NP}$$s$$O(s)$$O(s)$ variables de Cook-Levin.

Cela ne contredirait pas directement l'ETH car c'est pour les algorithmes déterministes.

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