?

Ist es möglich , dass ? Gibt es interessante Konsequenzen einer solchen Eindämmung? Würde es der Exponential Time Hypothese widersprechen?$\overline{SAT} \in NTIME(\exp(n^{0.9}))$

Es ist möglich ;-)

Es würde neue Schaltungsuntergrenzen geben. Da Sie eine ziemlich starke Annahme treffen, die sich aus der wegweisenden Arbeit von Impagliazzo, Kabanets und Wigderson ergeben könnte , habe ich das nicht überprüft.

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

Dies würde der ETH nicht direkt widersprechen, da dies für deterministische Algorithmen gilt.

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