Family 378Theoretical computer scienceLean67 pp · Oct 25, 2026

The Exponential Time Hypothesis is False

What this paper proves

For each fixed

k\ge2

, a deterministic algorithm counts the satisfying assignments of a

k

-CNF with

n

variables and

m

clauses in

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

time and polynomial space, and in

2^{O_{k,D}(n/\sqrt{\log n})}

times a polynomial when

m\le Dn

. The core is a subexponential contraction of bipartite tensor networks, built from a measurement design that splits the variables into groups so each clause depends freely only on its own group and on the others only through a few linear measurements. Since counting decides 3-SAT in

2^{o(n)}

time, this refutes ETH, which asserts 3-SAT needs

2^{\Omega(n)}

time.

Main theorem

theoremnovelSubexponential deterministic k-CNF model countingthm:main

For each fixed

k\ge2

, a deterministic algorithm counts the satisfying assignments

\#F

of a

k

-CNF on

n\ge20

variables with

m

clauses in

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

time and polynomial space. If

m\le Dn

for a fixed

D

, the time improves to

(n+m)^{O_{k,D}(1)}2^{O_{k,D}(n/\sqrt{\log n})}

Theorem 1.1 · as stated in the paper

For each fixed

k\ge2

, there exists a deterministic algorithm that, given a

k

-CNF

F

n\ge20

declared variables with

m

clauses, computes

\#F

as defined in in

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

bit operations and

(n+m)^{O_k(1)}

bits of space. For each fixed

D>0

, its running time on inputs with

m\le Dn

(n+m)^{O_{k,D}(1)}2^{O_{k,D}(n/\sqrt{\log n})}.

Where the new idea lives · 5 novel steps (one is the main theorem)

Definition 2.1Measurement design separating clause dependence

(r,\tau,D)

-design at

t

splits the variables into

r

groups of size at most

2n/r

, assigns each clause

e

to one group

\sigma_e(t)

, and gives each group an integer measurement matrix

C_g

with at most

2\tau n

rows in total and row coefficient sums at most

D

. Each clause's replacement linear forms depend freely only on its own group, and on every other group

S_h

only through the measurements

y_h=C_hx_h

Definition 3.1Layout of partitions, measurements, and polynomial rows

A layout is the data: for each of

Q

points

t

, a partition of

[n]

into

r

parts of size at most

2n/r

; for each factor

f

, a group assignment

\sigma_f\in[r]^Q

; for each

t,g

, an integer measurement matrix

C_{t,g}

with row weights at most

D

and total row count at most

2\tau n

over

g

; and for each

f

and

v\in I_f

, a rational polynomial row

\vec P_{f,v}(T)

of degree at most

R

with

\vec P_{f,v}(0)=\delta_v

. The row must vanish on any

\xi

killed by

C_{t,g}

whenever

g\ne\sigma_f(t)

, and

d_{\mathrm{den}}\vec P_{f,v}

has integer coefficients with

O(Q\log Q+\log D)

bits, where

d_{\mathrm{den}}=(R-1)!Q!

Theorem D.1Subexponential Boolean tensor network contraction

A bipartite tensor network with at most

Cs

edges, maximum degree at most

\lceil s^{9/10}\rceil

, and entries in

(\mathbb Z/2^{P_0}\mathbb Z)[V]/(V^\ell)

can be contracted deterministically in

(s+\mathcal L)^{O(1)}2^{O(s/\sqrt{\log s})}

bit operations and polynomial space. This holds provided each entry is computable in time

(s+\mathcal L)^b2^{As^{9/10}}

and polynomial space, and

\ell=1

is allowed.

Lemma D.2Counting zeros of sparse polynomial systems

For

a\le cn

polynomials over

\mathbb F_2

n\ge20

Boolean variables, each given as at most

\lceil\log_2 n\rceil^c

monomials of degree at most

k

, the number of common zeros can be computed deterministically in

n^{O_{k,c}(1)}2^{O_{k,c}(n\log\log n/\sqrt{\log n})}

bit operations and polynomial space.

Shape of the proof

novel otherOpen the graph →

statements mapped

sections

novel steps

friction flags

Map

The proof as a tree and a dependency graph. Start at the top and click down.

Read the paper

The PDF with the map beside it; every statement is linked.

Ask

Questions answered with citations to the map you can click.