Best Upper Bounds on SAT In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT."

I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time complexity of the most efficient SAT solver?

In particular, is it conceivable to find a sub-exponential (yet super-polynomial) algorithm for SAT?
There are two kinds of &quot;best&quot; SAT solvers, one for theory, one for practice.
Theory

Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki, &quot;Improved Randomized Algorithms for 3-SAT&quot;, ISAAC 2010.


randomized $O(1.32113^n)$ for 3SAT.


Timon Hertli, Robin A. Moser, Dominik Scheder, &quot;Improving PPSZ for 3-SAT using Critical Variables&quot;, 2011.


randomized $O(1.321^n)$ for 3SAT.


Konstantin Kutzkov, Dominik Scheder, &quot;Using CSP To Improve Deterministic 3-SAT&quot;, 2010.


deterministic $O(1.439^n)$ for 3SAT.

Practice
Check SAT conference for competition results for each year.