Exponential Time Hypothesis (ETH)
DefinitionSubspaceConv_Supplement_ETHfine-grained-complexitygraph-coloringp2o-gran-per-chapterp2o-plan-paperp2o-v1rank-width
The Exponential Time Hypothesis [IP01]: there is such that no deterministic algorithm decides satisfiability of 3-CNF formulas with variables in time .
It is the hypothesis of Theorems 8 and 9. The paper notes (p.4, footnote 2) that a recent preprint [Cla26] reports subexponential 3-SAT algorithms, which would refute ETH; the theorems are implications and are stated as such.
Formalization Note Algorithms are published multi-tape CookLevin Turing machines; an instance is the published code encode3SAT n φ of a 3-CNF formula on variables (published Is3CNFOn: clauses of at most three literals, variables below , no repeated clause); deciding is the published DecidesIn. ETH is a proposition used only as a hypothesis, never an axiom.
Definition code
import Mathlib
import Definitions.Def_CookLevin_Cost
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_HiddenPartition_Supplement_AlmostETH
set_option autoImplicit false
open Classical
namespace SubspaceConv.Supplement
/-- The **Exponential Time Hypothesis** [IP01], as assumed in Theorems 8 and 9 of Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2)
(p.4, 27, 30; PDF p.5, 28, 31): there is `δ > 0` such that no deterministic algorithm decides
satisfiability of 3-CNF formulas on `n` variables in time `O(2^{δn})`.
**Formalization Note** An algorithm is a published multi-tape `CookLevin.TuringMachine`, run by
the published step interpreter; "time `O(2^{δn})`" is one constant `C` such that on the code
`encode3SAT n φ` (published, `n` in unary then the formula) of every 3-CNF formula `φ` on `n`
variables (published `Is3CNFOn`: clauses of at most three literals, variables below `n`, no
repeated clause, so the number of clauses is polynomial in `n`) the machine halts within
`C · 2^{δn}` steps with verdict `[φ satisfiable]` (published `DecidesIn`). A `Prop`, used only as a
hypothesis. -/
def ETH : Prop :=
∃ δ : ℝ, 0 < δ ∧
¬ ∃ (M : CookLevin.Machine) (k g : ℕ) (C : ℝ), CookLevin.TuringMachine k g M ∧
∀ (n : ℕ) (φ : CookLevin.Formula), HiddenPartition.Supplement.Is3CNFOn n φ →
∃ t : ℕ, (t : ℝ) ≤ C * (2 : ℝ) ^ (δ * n) ∧
CookLevin.DecidesIn M k
(CookLevin.boolsToSymbols (HiddenPartition.Supplement.encode3SAT n φ)) [] t
(decide (CookLevin.Satisfiable φ))
end SubspaceConv.Supplement
Source
Perles, Weinstein, A Fast Algorithm for Subspace Convolution, STOC 2027 submission manuscript (sha256 a8ffb1b4e583122875209a3e25ee95aa3a7af933526e165d47c274634e604ab2), p.4 (PDF p.5) and App. G–H; [IP01]