The Exponential Time Hypothesis is False

If you have an expression in n Boolean variables, how long does it take to find out whether some assignment of values to the variables makes the expression true? There is an obvious upper bound: you can find out in 2n steps by exhaustive search, trying all possible ways of setting each variable to true or false. You can often do better than exhaustive search for a particular problem, but can you always do better, even in the worst case? The Monien–Speckenmeyer branching algorithm, published in 1985, is more efficient than exhaustive search, but it still takes exponential time. 3-SAT The Boolean satisfiability problem (SAT) asks whether a Boolean expression in conjunctive normal form (CNF) can be satisfied by some assignment of values to the variables. The k-SAT problem is the special case of SAT in which each no clause contains more than k variables. The 2-SAT problem can be solved in polynomial time, but the case of the 3-SAT problem is unknown. The 3-SAT problem is NP-complete, and…