Return to Answer

It is impossible for 3SAT to have sub-exponential algorithms unless the exponential time hypothesis (ETH) is false.

For the Upper bound, 3-SAT has randomized algorithm with expected running time $O({1.324}^n)$

Improved upper bounds for 3-SAT, Kazuo Iwama, Suguru Tamaki, foo

Actually, Daniel Rolf improved Kazuo Iwama, Suguru Tamaki result to $O({1.32216}^n)$

Improved Bound for the PPSZ/Schoning-Algorithm for 3-SAT, Daniel Rolf,

It is impossible for 3SAT to have sub-exponential algorithms unless the exponential time hypothesis is false.

• Kazuo Iwama, Suguru Tamaki, Improved upper bounds for 3-SAT, 2004.

randomized algorithm with expected running time $O({1.324}^n)$ for 3SAT.

• Daniel Rolf, Improved Bound for the PPSZ/Schoning-Algorithm for 3-SAT, 2005.

randomized algorithm with expected running time $O({1.32216}^n)$ for 3SAT.

It is impossible for 3SAT to have sub-exponential algorithms unless the exponential time hypothesis (ETH) is false.

For the Upper bound, 3-SAT has randomized algorithm with expected running time $O({1.324}^n)$

Improved upper bounds for 3-SAT, Kazuo Iwama, Suguru Tamaki, foo

It is impossible for 3SAT to have sub-exponential algorithms unless the exponential time hypothesis (ETH) is false.

For the Upper bound, 3-SAT has randomized algorithm with expected running time $O({1.324}^n)$

Improved upper bounds for 3-SAT, Kazuo Iwama, Suguru Tamaki, foo

Actually, Daniel Rolf improved Kazuo Iwama, Suguru Tamaki result to $O({1.32216}^n)$

Improved Bound for the PPSZ/Schoning-Algorithm for 3-SAT, Daniel Rolf,

It is impossible for 3SAT to have sub-exponential algorithms unless the exponential time hypothesis (ETH) is false.

For the Upper bound, 3-SAT has randomized algorithm with expected running time $O(2^{1.324n})$

Improved upper bounds for 3-SAT, Kazuo Iwama, Suguru Tamaki, foo

It is impossible for 3SAT to have sub-exponential algorithms unless the exponential time hypothesis (ETH) is false.

For the Upper bound, 3-SAT has randomized algorithm with expected running time $O({1.324}^n)$

Improved upper bounds for 3-SAT, Kazuo Iwama, Suguru Tamaki, foo