?

Apakah mungkin bahwa ? Adakah konsekuensi menarik dari penahanan seperti itu? Apakah itu bertentangan dengan Hipotesis Waktu Eksponensial?$\overline{SAT} \in NTIME(\exp(n^{0.9}))$

Itu mungkin ;-)

Ini akan memberi batas sirkuit baru lebih rendah. Karena Anda membuat asumsi yang cukup kuat, ini bisa mengikuti dari karya mani oleh Impagliazzo, Kabanets, dan Wigderson , saya belum memeriksa.

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

Itu tidak akan secara langsung bertentangan dengan ETH karena itu untuk algoritma deterministik.

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