Theorem 8 — under ETH no algorithm decides on supplied layouts or rank-decompositions
OpenSubspaceConv.Supplement.theorem_8Assume the Exponential Time Hypothesis. Then for every computable function and every fixed there is no algorithm that decides whether in time
on -vertex graphs supplied with a linear layout of width , where is part of the input. The same exclusion holds with a supplied rank-decomposition of width .
Together with Theorem 6, whose running time is , this shows that the leading coefficient in the doubly exponential exponent is optimal under ETH.
Formalization Note Algorithms are published multi-tape CookLevin machines, deciding in the published DecidesIn sense, on the input (code of , code of the layout or decomposition, in unary); is the actual width of the supplied structure; the power of is real; computability of is Mathlib's Computable.
Differences from the source:
- encoding: ETH [IP01]; an algorithm and its running time (no machine named) → SubspaceConv.Supplement.ETH as a hypothesis; algorithms are published CookLevin multi-tape machines on fixed bit codes, time is their step count; reason: the standard 2^{δn} form of ETH; the paper leaves the machine model unspecified (p.4)
- generalization: algorithms on all N-vertex graphs with a layout → the excluded algorithm need only work on graphs with N ≥ 1 (layout clause); reason: at N = 0 the bound f(r)·0^{…} is 0 steps, which no machine meets, so including N = 0 would make the exclusion trivial; excluding algorithms correct on fewer inputs is stronger and implies the paper's statement
- generalization: algorithms on all N-vertex graphs with a rank-decomposition → the excluded algorithm need only work on the inputs that carry a published BranchDecomp (N ≥ 2); reason: rank-decompositions are defined for |V| ≥ 2 only; excluding algorithms correct on fewer inputs is stronger and implies the paper's statement
import Mathlib import Definitions.Def_CookLevin_Basic import Definitions.Def_CookLevin_Cost import Definitions.Def_CookLevin_Satisfiability import Definitions.Def_ApproxCliqueWidth_Certificate_CutRank import Definitions.Def_ApproxCliqueWidth_Certificate_BranchDecomp import Definitions.Def_SubspaceConv_Supplement_layoutWidth import Definitions.Def_SubspaceConv_Supplement_rdWidth import Definitions.Def_SubspaceConv_Supplement_graphCode import Definitions.Def_SubspaceConv_Supplement_chromPoly import Definitions.Def_SubspaceConv_Supplement_ETH set_option autoImplicit false open Classical
namespace SubspaceConv.Supplement
/-- **Theorem 8**, Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), App. G, p.27 (PDF p.28). Assuming ETH, for every computable function `f`
and fixed `α ≥ 0`, there is no algorithm deciding whether `χ(G) ≤ η` in time
`f(r) N^{α + 2^{r²/4 − 17r}}` on `N`-vertex graphs supplied with a linear layout of width `r`, where
`η` is part of the input. The same exclusion holds with a supplied rank-decomposition of width `r`.
**Formalization Note** ETH is `SubspaceConv.Supplement.ETH` (a hypothesis). An algorithm is a
published multi-tape `CookLevin.TuringMachine`; time is steps of the published interpreter, and
"deciding" is the published `DecidesIn` with verdict `[χ(G) ≤ η]`. The input is
`graphCode G ++ layoutCode π ++ encodeNat η` (resp. `graphCode G ++ rdCode D ++ encodeNat η`);
`r` is the actual width of the supplied layout (`layoutWidth`) or decomposition (`rdWidth`); the
power of `N` is a real power. `f : ℕ → ℕ` is computable in Mathlib's sense (`Computable`). For
layouts the hypothetical algorithm is only required on graphs with `N ≥ 1`: at `N = 0` the bound
`f(r) · 0^{…}` is `0` steps, which no machine meets; dropping that instance only strengthens the
exclusion. Rank-decompositions exist only for `N ≥ 2`. -/
theorem theorem_8 (hETH : ETH) (f : ℕ → ℕ) (hf : Computable f) (α : ℝ) (hα : 0 ≤ α) :
(¬ ∃ (M : CookLevin.Machine) (k g : ℕ), CookLevin.TuringMachine k g M ∧
∀ (N : ℕ), 1 ≤ N → ∀ (G : SimpleGraph (Fin N)) [DecidableRel G.Adj] (π : Fin N ≃ Fin N)
(η : ℕ), ∃ t : ℕ,
(t : ℝ) ≤ (f (layoutWidth G π) : ℝ) * (N : ℝ) ^ (α + (2 : ℝ) ^
((layoutWidth G π : ℝ) ^ 2 / 4 - 17 * (layoutWidth G π : ℝ))) ∧
CookLevin.DecidesIn M k
(CookLevin.boolsToSymbols (graphCode G ++ layoutCode π ++ CookLevin.encodeNat η)) [] t
(decide (chromNum G ≤ η))) ∧
(¬ ∃ (M : CookLevin.Machine) (k g : ℕ), CookLevin.TuringMachine k g M ∧
∀ (N : ℕ) (G : SimpleGraph (Fin N)) [DecidableRel G.Adj]
(D : ApproxCliqueWidth.Certificate.BranchDecomp (Fin N)) (η : ℕ), ∃ t : ℕ,
(t : ℝ) ≤ (f (rdWidth G D) : ℝ) * (N : ℝ) ^ (α + (2 : ℝ) ^
((rdWidth G D : ℝ) ^ 2 / 4 - 17 * (rdWidth G D : ℝ))) ∧
CookLevin.DecidesIn M k
(CookLevin.boolsToSymbols (graphCode G ++ rdCode D ++ CookLevin.encodeNat η)) [] t
(decide (chromNum G ≤ η))) := by sorry
end SubspaceConv.Supplement