> Despite a remarkable amount of algorithmic effort on Boolean satisfiability (SAT) and related problems, to date no one has invented an algorithm with faster-t

> Despite a remarkable amount of algorithmic effort on Boolean satisfiability (SAT) and related problems, to date no one has invented an algorithm with faster-than-exponential (O(2^n)) running time; indeed, there is no polynomial-time algorithm for SAT unless P = NP. [1] https://www.hindawi.com/journals/complexity/2018/7982851/ [2] http://www.cs.cornell.edu/~sabhar/publications/learnIJCAI03.pdf The [1] shows how to replace numerical problem solving process with the SAT (circuit) based one and obtain exponential speed up. Let me quote the [2]: "We also show that without restarts but with a new learning scheme, clause learning can provide exponentially smaller proofs than regular resolution, which itself is known to be much stronger than ordinary DPLL." So, in my opinion, there are algorithms that work in O(2^(n(1-e))) time.