Counting Exponential Time Hypothesis (#ETH)
DefinitionSubspaceConv_Supplement_SharpETHfine-grained-complexitygraph-coloringp2o-gran-per-chapterp2o-plan-paperp2o-v1rank-width
The counting Exponential Time Hypothesis #ETH [DHM+14]: there is such that no deterministic algorithm computes the number of satisfying assignments of 3-CNF formulas with variables in time .
It is the hypothesis of Theorem 10. The paper states it as excluding time for clauses; for 3-CNF formulas without repeated clauses , so the factor is absorbed.
Formalization Note Same machines and instances as ETH; the output is the number of satisfying assignments of in binary on the last tape, within the time bound in the sense of the published HiddenPartition.Supplement.OutputsWithin. A proposition used only as a hypothesis.
Definition code
import Mathlib
import Definitions.Def_CookLevin_Cost
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_HiddenPartition_Supplement_AlmostETH
import Definitions.Def_DetParamSVP_RunsWithin
import Definitions.Def_HiddenPartition_Supplement_encodeLabels
set_option autoImplicit false
open Classical
namespace SubspaceConv.Supplement
/-- The number of satisfying assignments `x_0, …, x_{n−1}` of a formula `φ`: assignments
`Fin n → Bool`, extended by `false` beyond `n` (irrelevant for formulas on `n` variables). -/
noncomputable def satCount (n : ℕ) (φ : CookLevin.Formula) : ℕ :=
Fintype.card {α : Fin n → Bool //
CookLevin.Satisfies (fun i => if h : i < n then α ⟨i, h⟩ else false) φ}
/-- The **counting Exponential Time Hypothesis** `#ETH` [DHM+14], as assumed in Theorem 10 of
Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2) (p.30–31, PDF p.31–32: "#ETH excludes 2^{o(n)} poly(m) time for counting satisfying
assignments of 3-CNF formulas with n variables and m clauses"): there is `δ > 0` such that no
deterministic algorithm outputs the number of satisfying assignments of 3-CNF formulas on `n`
variables in time `O(2^{δn})`.
**Formalization Note** Same machine model and instances as `SubspaceConv.Supplement.ETH`; the
output is the count in binary (`Nat.bits`) on the last tape (published `HiddenPartition.Supplement.OutputsWithin`). The number `m` of
distinct clauses of a 3-CNF formula on `n` variables is at most `(2n + 1)^3`, so `poly(m)` factors
are absorbed in `2^{δn}`. A `Prop`, used only as a hypothesis. -/
def SharpETH : Prop :=
∃ δ : ℝ, 0 < δ ∧
¬ ∃ (M : CookLevin.Machine) (k g : ℕ) (C : ℝ), CookLevin.TuringMachine k g M ∧
∀ (n : ℕ) (φ : CookLevin.Formula), HiddenPartition.Supplement.Is3CNFOn n φ →
HiddenPartition.Supplement.OutputsWithin M k (HiddenPartition.Supplement.encode3SAT n φ)
(C * (2 : ℝ) ^ (δ * n)) (Nat.bits (satCount n φ))
end SubspaceConv.Supplement
Source
Perles, Weinstein, A Fast Algorithm for Subspace Convolution, STOC 2027 submission manuscript (sha256 a8ffb1b4e583122875209a3e25ee95aa3a7af933526e165d47c274634e604ab2), App. H, p.30–31 (PDF p.31–32); [DHM+14]