0
$\begingroup$

Assuming the Exponential time hypothesis is true, what's the fast possible algorithm that can be produced for NP-complete problems?

If 3-Sat takes exponential time, then could it be possible that some NP-complete problems can be solved in $n^{log^k(n)}$ time? $2^{n^{1/log(log(n))}}$ time? $2^{n^{0.5}}$ time?

$\endgroup$