The Exponential Time Hypothesis is False
For every fixed , there exists a deterministic algorithm that counts the satisfying assignments of an arbitrary -CNF formula on variables and clauses in time and space, which refutes the Exponential Time Hypothesis (ETH).
The algorithmic bounds in Theorem 1.1 are fully proved, and deciding 3-SAT via #3-SAT > 0 in 2^{o(n)} (n + m)^{O(1)} deterministic time directly contradicts ETH.
“We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula. For every fixed k >= 2, on a formula with n variables and m clauses, our algorithm uses poly_k(n, m) space and runs in time (n + m)^{O_k(1)} 2^{n/(log n)^{1/2 + o(1)}}. Our algorithm refutes the Exponential Time Hypothesis (ETH), which postulates that deciding 3-SAT on n variables requires 2^{\Omega(n)} time in the worst case.” · Show in paper