Theorem 1.3 — FPT implies quasipolynomial time for every r.e. hypergraph class
OpenSparseIncidenceHom.WidthComparison.Supplement.theorem_1_3homomorphismsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexityquasipolynomial-time
Let be a recursively enumerable hypergraph class, and assume . If -, then can be solved in time
where is the input size. That is, some deterministic algorithm answers every promise instance (with ) correctly, and there are a function and a threshold such that on every promise instance of size it halts within steps. The function and the threshold may depend on .
No sparsity assumption on is made: fixed-parameter tractability alone yields a quasipolynomial algorithm.
Formalization Note Classes, machines and the time bound are those of the definition item SparseIncidenceHom.WidthComparison.Supplement.Problems; is the length of the input string, which is .
Differences from the source:
- generalization: every member of a hypergraph class is nonempty and connected (p. 7: "We assume input hypergraphs are nonempty and connected") → classes may contain empty or disconnected hypergraphs (every H_A of a structure, published FiniteHypergraph without InputHypergraph); reason: on a class of nonempty connected hypergraphs the Lean statement is the source's; widths, incidence degeneracy, boundedness of α and Hom decompose over connected components, and the empty hypergraph has every width 0
- encoding: a recursively enumerable hypergraph class with membership up to isomorphism → a set of hypergraph codes (n, edge lists) that is an r.e. predicate, H belonging to it when some code describes H up to isomorphism; reason: Lean convention for classes; the same classes
- encoding: FPT, and solvable in time N^{(log N)^{1+o(1)}} → deterministic multi-tape machines of the published Cook–Levin cost model: within f(k)·(|x|+1)^c steps (f computable), resp. correct on every promise instance and halting within N^{(log₂ N)^{1+ε(N)}} steps for N ≥ N₀, with ε(N) → 0; reason: standard machine model; the quasipolynomial bound is unchanged by polynomial changes of model or encoding
- encoding: ‖H_A‖, the length of the list of edges as vertex lists → Σ_e (|e|+1); reason: each is bounded by a computable function of the other, so FPT membership is unchanged
- encoding: ‖A‖ + ‖B‖, explicit tuple lists → the length of the concatenated self-delimiting unary encodings of A and B; reason: polynomially related to any standard encoding, which the bound N^{(log N)^{1+o(1)}} absorbs
- encoding: FPT ≠ W[1] → some problem FPT-reducible to p-Clique (published InW1) is not in FPT; reason: equivalent, since FPT ⊆ W[1]
Preamble
import Mathlib import Definitions.Def_SparseIncidenceHom_WidthComparison_Supplement_Problems
Formal statement
namespace SparseIncidenceHom.WidthComparison.Supplement
open SparseIncidenceHom.WidthComparison
/-- Lanzinger, STOC 2027 submission #662, Theorem 1.3, p. 5. -/
theorem theorem_1_3 (𝓗 : HypergraphClass) (hre : IsREClass 𝓗) (hW : FPTneW1)
(hfpt : InFPT (pHomHyp 𝓗)) :
SolvableInQuasiPolyTime (homHyp 𝓗) := by sorry
end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), p. 5, Theorem 1.3; proof pp. 15–16