Family 378Theoretical computer scienceLeanDigested

Disproof of the Exponential Time Hypothesis

For every fixed

k\ge2

, a deterministic algorithm counts the satisfying assignments of a

k

-CNF with

n

variables and

m

clauses in time

(n+m)^{O_k(1)}2^{n/(\log n)^{1/2+o(1)}}

. This yields superlinear circuit lower bounds for a language in

\mathsf{E}^{\mathsf{NP}}

on infinitely many input lengths.

Manuscripts in this family · 1

Oct 25, 2026·67 pp·paper.pdfDigestedLean

We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary

k

-CNF formula. For every fixed

k\ge2

, on a formula with

n

variables and

m

clauses, our algorithm uses space polynomial in

n

and

m

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.

Full abstract