Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Hypergraph and structure classes, PTIME, FPT, FPT≠W[1]\mathrm{FPT}\ne\mathrm{W}[1]FPT=W[1], quasipolynomial time, and the homomorphism problems

Definition
SparseIncidenceHom_WidthComparison_Supplement_Problems

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

homomorphismshypergraph-classesp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexitypromise-problems

Classes. A hypergraph is coded by (n,edges)(n,\text{edges})(n,edges): vertex set {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1} and a list of edges, each a list of vertices. A hypergraph class H\mathcal HH is a set of codes; a hypergraph HHH belongs to H\mathcal HH (up to isomorphism) if some code in H\mathcal HH describes a hypergraph isomorphic to HHH. H\mathcal HH is recursively enumerable if its set of codes is. H\mathcal HH has bounded width www if sup⁡H∈Hw(H)<∞\sup_{H\in\mathcal H}w(H)<\inftysupH∈H​w(H)<∞, and bounded incidence degeneracy or primal independence if sup⁡H∈Hμ(H)<∞\sup_{H\in\mathcal H}\mu(H)<\inftysupH∈H​μ(H)<∞ or sup⁡H∈Hα(H)<∞\sup_{H\in\mathcal H}\alpha(H)<\inftysupH∈H​α(H)<∞. A structure class A\mathcal AA is a set of structure codes; only its well-formed members count (an ill-formed code denotes no structure), and a structure belongs to A\mathcal AA when it is isomorphic to a well-formed member. The class has bounded incidence degeneracy if sup⁡A∈Aμ(HA)<∞\sup_{A\in\mathcal A}\mu(H_A)<\inftysupA∈A​μ(HA​)<∞, and core⁡(A)\operatorname{core}(\mathcal A)core(A) has bounded width www if sup⁡A∈Aw(Hcore⁡(A))<∞\sup_{A\in\mathcal A}w(H_{\operatorname{core}(A)})<\inftysupA∈A​w(Hcore(A)​)<∞. The hypergraph size is ∥H∥=∑e∈E(H)(∣e∣+1)\|H\|=\sum_{e\in E(H)}(|e|+1)∥H∥=∑e∈E(H)​(∣e∣+1).

Complexity. A promise problem has yes-instances and no-instances; an algorithm solves it if it answers correctly on every instance of either kind, with no requirement elsewhere. Machines are the deterministic multi-tape Turing machines of the published Cook–Levin cost model. PTIME\mathrm{PTIME}PTIME: a machine answers within c(∣x∣+1)dc(|x|+1)^dc(∣x∣+1)d steps. FPT\mathrm{FPT}FPT (for a problem with parameter kkk): a machine started on the pair (x,k)(x,k)(x,k) answers within f(k)(∣x∣+1)cf(k)(|x|+1)^cf(k)(∣x∣+1)c steps for a computable fff. W[1]\mathrm{W}[1]W[1] is the class of parameterized problems FPT-reducible to ppp-Clique, and FPT≠W[1]\mathrm{FPT}\ne\mathrm{W}[1]FPT=W[1] means that some problem of W[1]\mathrm{W}[1]W[1] is not in FPT\mathrm{FPT}FPT. A promise problem is solvable in time N(log⁡N)1+o(1)N^{(\log N)^{1+o(1)}}N(logN)1+o(1) if a machine answers every instance correctly and there are ε(N)→0\varepsilon(N)\to0ε(N)→0 and N0N_0N0​ such that on instances of length N≥N0N\ge N_0N≥N0​ it halts within

N(log⁡2N)1+ε(N)N^{(\log_2 N)^{1+\varepsilon(N)}}N(log2​N)1+ε(N)

steps.

Problems. Hom(H)\mathrm{Hom}(\mathcal H)Hom(H): input well-formed structures A,BA,BA,B over the same signature, encoded as the concatenation of their encodings (length N=∥A∥+∥B∥N=\|A\|+\|B\|N=∥A∥+∥B∥), with HA∈HH_A\in\mathcal HHA​∈H; question A→BA\to BA→B. ppp-Hom(H)\mathrm{Hom}(\mathcal H)Hom(H) is the same problem with parameter ∥HA∥\|H_A\|∥HA​∥. Hom(A)\mathrm{Hom}(\mathcal A)Hom(A) and ppp-Hom(A)\mathrm{Hom}(\mathcal A)Hom(A) have the promise A∈AA\in\mathcal AA∈A and parameter ∥A∥\|A\|∥A∥.

These notions state Theorems 1.2–1.4, 4.1, 4.3, Proposition 4.2 and Lemmas 6.1–6.2.

Formalization Note W[1], FPT reductions, promise problems and promise W[1]-hardness are the published SerialBatchTardy.InW1, DetParamSVP.PromiseProblem and DetParamSVP.PromiseW1Hard; the parameter is supplied beside the string and must equal ∥HA∥\|H_A\|∥HA​∥ (resp. ∥A∥\|A\|∥A∥) on promise instances. Codes describing nothing (an empty listed edge, an uncovered vertex) contribute no member; listed edges with out-of-range vertices are ignored, which does not change which classes are recursively enumerable.

Definition code
import Mathlib
import Definitions.Def_DetParamSVP_Promise
import Definitions.Def_SparseIncidenceHom_WidthComparison_Supplement_Structures
import Definitions.Def_SparseIncidenceHom_WidthComparison_Supplement_Widths

namespace SparseIncidenceHom.WidthComparison.Supplement

open SparseIncidenceHom.WidthComparison

/-! ### Hypergraph classes -/

/-- A hypergraph code `(n, edges)`: vertex set `{0, …, n-1}` and a list of edges, each a list of
vertices (footnote 1, p. 3). -/
abbrev HCode : Type := ℕ × List (List ℕ)

/-- The code `c` describes `H` up to isomorphism: some bijection `V ≃ {0, …, n-1}` maps the edge
set of `H` exactly onto the sets of entries of the listed edges. -/
def Describes (c : HCode) {V : Type} (H : FiniteHypergraph V) : Prop :=
  ∃ σ : V ≃ Fin c.1, ∀ S : Set V,
    S ∈ H.graph.edgeSet ↔ ∃ l ∈ c.2, (fun v => ((σ v : Fin c.1) : ℕ)) '' S = {a | a ∈ l}

/-- A hypergraph class, given by the codes of its members. -/
abbrev HypergraphClass : Type := Set HCode

/-- Membership up to isomorphism. -/
def InClass (𝓗 : HypergraphClass) {V : Type} (H : FiniteHypergraph V) : Prop :=
  ∃ c ∈ 𝓗, Describes c H

/-- A recursively enumerable class: its set of codes is r.e. -/
def IsREClass (𝓗 : HypergraphClass) : Prop := REPred (fun c : HCode => c ∈ 𝓗)

/-- `H` has bounded width `w`: one real bound for `w` on every member (members are represented
on `Fin n`; membership is isomorphism invariant). -/
def BoundedWidth (𝓗 : HypergraphClass) (w : ∀ n : ℕ, FiniteHypergraph (Fin n) → ℝ) : Prop :=
  ∃ c : ℝ, ∀ (n : ℕ) (H : FiniteHypergraph (Fin n)), InClass 𝓗 H → w n H ≤ c

/-- Bounded incidence degeneracy or bounded primal independence number of the class. -/
def BoundedDegeneracyOrIndependence (𝓗 : HypergraphClass) : Prop :=
  (∃ d : ℕ, ∀ (n : ℕ) (H : FiniteHypergraph (Fin n)), InClass 𝓗 H → incidenceDegeneracy H ≤ d) ∨
  (∃ d : ℕ, ∀ (n : ℕ) (H : FiniteHypergraph (Fin n)), InClass 𝓗 H → independenceNumber H ≤ d)

/-- `‖H‖` (footnote 1, p. 3): listing the edges, each as a list of its vertices, one symbol per
vertex occurrence plus one delimiter per edge. -/
noncomputable def hypergraphNorm {V : Type} [Fintype V] (H : FiniteHypergraph V) : ℕ :=
  ∑ e : Edge H, (e.val.ncard + 1)

/-! ### Structure classes -/

/-- A class of finite relational structures. -/
abbrev StructureClass : Type := Set RelStr

/-- Membership up to isomorphism, with respect to the well-formed members of the class (the actual
finite structures; an ill-formed code in `𝒜` denotes no structure and is ignored, exactly as in
`BoundedStructureDegeneracy`, `CoreBoundedFhw` and `CoreBoundedSubw`). -/
def InStructureClass (𝒜 : StructureClass) (A : RelStr) : Prop :=
  ∃ A' ∈ 𝒜, RelStr.WellFormed A' ∧ RelStr.Isomorphic A A'

/-- A recursively enumerable structure class. -/
def IsREStructureClass (𝒜 : StructureClass) : Prop := REPred (fun A : RelStr => A ∈ 𝒜)

/-- Bounded incidence degeneracy of `{H_A : A ∈ 𝒜}`. -/
def BoundedStructureDegeneracy (𝒜 : StructureClass) : Prop :=
  ∃ d : ℕ, ∀ A ∈ 𝒜, RelStr.WellFormed A → incidenceDegeneracy (RelStr.hypergraph A) ≤ d

/-- `core(𝒜)` has bounded fractional hypertree width (p. 16). -/
def CoreBoundedFhw (𝒜 : StructureClass) : Prop :=
  ∃ c : ℝ, ∀ A ∈ 𝒜, RelStr.WellFormed A → ∀ h : ℕ → ℕ, RelStr.IsCoreMap A h →
    fractionalHypertreeWidth (RelStr.hypergraph (RelStr.image A h)) ≤ c

/-- `core(𝒜)` has bounded submodular width (p. 17). -/
def CoreBoundedSubw (𝒜 : StructureClass) : Prop :=
  ∃ c : ℝ, ∀ A ∈ 𝒜, RelStr.WellFormed A → ∀ h : ℕ → ℕ, RelStr.IsCoreMap A h →
    submodularWidth (RelStr.hypergraph (RelStr.image A h)) ≤ c

/-! ### Machine-level complexity notions (published Cook–Levin cost model) -/

/-- A (non-parameterized) promise decision problem on binary strings. -/
structure DecisionPromise where
  yes : List Bool → Prop
  no : List Bool → Prop

/-- PTIME for a promise problem: a deterministic multi-tape machine halts within `c·(|x|+1)^d`
steps with the correct verdict on every promise input. -/
def InPTIME (P : DecisionPromise) : Prop :=
  ∃ (M : CookLevin.Machine) (m G c d : ℕ), CookLevin.TuringMachine m G M ∧
    ∀ x : List Bool,
      (P.yes x → CookLevin.DecidesIn M m (CookLevin.boolsToSymbols x) []
        (CookLevin.polyBound c d x.length) true) ∧
      (P.no x → CookLevin.DecidesIn M m (CookLevin.boolsToSymbols x) []
        (CookLevin.polyBound c d x.length) false)

/-- FPT for a parameterized promise problem: started on `paramCode x k`, a machine halts within
`f(k)·(|x|+1)^c` steps (`f` computable) with the correct verdict on every promise input. -/
def InFPT (P : DetParamSVP.PromiseProblem) : Prop :=
  ∃ (M : CookLevin.Machine) (m G : ℕ) (f : ℕ → ℕ) (c : ℕ),
    CookLevin.TuringMachine m G M ∧ Computable f ∧
    ∀ (x : List Bool) (k : ℕ),
      (P.yes x k → CookLevin.DecidesIn M m
        (CookLevin.boolsToSymbols (SerialBatchTardy.paramCode x k)) []
        (CookLevin.polyBound (f k) c x.length) true) ∧
      (P.no x k → CookLevin.DecidesIn M m
        (CookLevin.boolsToSymbols (SerialBatchTardy.paramCode x k)) []
        (CookLevin.polyBound (f k) c x.length) false)

/-- `FPT ≠ W[1]`: some problem of W[1] (published `SerialBatchTardy.InW1`) is not in FPT.
Since FPT ⊆ W[1], this is the class inequality. -/
def FPTneW1 : Prop :=
  ∃ Q : SerialBatchTardy.ParamProblem, SerialBatchTardy.InW1 Q ∧ ¬ InFPT (DetParamSVP.ofLanguage Q)

/-- Solvable in time `N^{(log N)^{1+o(1)}}`: a machine decides every promise input correctly, and
for some `ε(N) → 0` it halts within `N^{(log₂ N)^{1+ε(N)}}` steps on every promise input of
length `N ≥ N₀`. -/
def SolvableInQuasiPolyTime (P : DecisionPromise) : Prop :=
  ∃ (M : CookLevin.Machine) (m G : ℕ) (ε : ℕ → ℝ) (N₀ : ℕ),
    CookLevin.TuringMachine m G M ∧ Filter.Tendsto ε Filter.atTop (nhds 0) ∧
    ∀ x : List Bool,
      (P.yes x → ∃ t : ℕ, CookLevin.DecidesIn M m (CookLevin.boolsToSymbols x) [] t true ∧
        (N₀ ≤ x.length →
          (t : ℝ) ≤ (x.length : ℝ) ^ ((logTwo (x.length : ℝ)) ^ (1 + ε x.length)))) ∧
      (P.no x → ∃ t : ℕ, CookLevin.DecidesIn M m (CookLevin.boolsToSymbols x) [] t false ∧
        (N₀ ≤ x.length →
          (t : ℝ) ≤ (x.length : ℝ) ^ ((logTwo (x.length : ℝ)) ^ (1 + ε x.length))))

/-! ### The homomorphism problems -/

/-- A valid input pair: well-formed structures over the same signature. -/
def IsHomInput (A B : RelStr) : Prop :=
  RelStr.WellFormed A ∧ RelStr.WellFormed B ∧ A.arities = B.arities

/-- `Hom(𝓗)` (p. 3): input `(A, B)` encoded as `encode A ++ encode B` (length `‖A‖ + ‖B‖`),
promise `H_A ∈ 𝓗`, question `A → B`. -/
def homHyp (𝓗 : HypergraphClass) : DecisionPromise where
  yes x := ∃ A B : RelStr, IsHomInput A B ∧ InClass 𝓗 (RelStr.hypergraph A) ∧
    x = RelStr.encode A ++ RelStr.encode B ∧ RelStr.HomTo A B
  no x := ∃ A B : RelStr, IsHomInput A B ∧ InClass 𝓗 (RelStr.hypergraph A) ∧
    x = RelStr.encode A ++ RelStr.encode B ∧ ¬ RelStr.HomTo A B

/-- `p-Hom(𝓗)` (p. 3): `Hom(𝓗)` parameterized by `‖H_A‖`, which must be the supplied parameter. -/
def pHomHyp (𝓗 : HypergraphClass) : DetParamSVP.PromiseProblem where
  yes x k := ∃ A B : RelStr, IsHomInput A B ∧ InClass 𝓗 (RelStr.hypergraph A) ∧
    x = RelStr.encode A ++ RelStr.encode B ∧ k = hypergraphNorm (RelStr.hypergraph A) ∧
    RelStr.HomTo A B
  no x k := ∃ A B : RelStr, IsHomInput A B ∧ InClass 𝓗 (RelStr.hypergraph A) ∧
    x = RelStr.encode A ++ RelStr.encode B ∧ k = hypergraphNorm (RelStr.hypergraph A) ∧
    ¬ RelStr.HomTo A B

/-- `Hom(𝒜)` (p. 16): promise `A ∈ 𝒜` (up to isomorphism), question `A → B`. -/
def homStruct (𝒜 : StructureClass) : DecisionPromise where
  yes x := ∃ A B : RelStr, IsHomInput A B ∧ InStructureClass 𝒜 A ∧
    x = RelStr.encode A ++ RelStr.encode B ∧ RelStr.HomTo A B
  no x := ∃ A B : RelStr, IsHomInput A B ∧ InStructureClass 𝒜 A ∧
    x = RelStr.encode A ++ RelStr.encode B ∧ ¬ RelStr.HomTo A B

/-- `p-Hom(𝒜)` (p. 16): `Hom(𝒜)` parameterized by the pattern, i.e. by `‖A‖`. -/
def pHomStruct (𝒜 : StructureClass) : DetParamSVP.PromiseProblem where
  yes x k := ∃ A B : RelStr, IsHomInput A B ∧ InStructureClass 𝒜 A ∧
    x = RelStr.encode A ++ RelStr.encode B ∧ k = RelStr.norm A ∧ RelStr.HomTo A B
  no x k := ∃ A B : RelStr, IsHomInput A B ∧ InStructureClass 𝒜 A ∧
    x = RelStr.encode A ++ RelStr.encode B ∧ k = RelStr.norm A ∧ ¬ RelStr.HomTo A B

end SparseIncidenceHom.WidthComparison.Supplement
Source
Matthias Lanzinger, STOC 2027 submission #662 (October 2026), pp. 3–6 (Hom(H), p-Hom(H), footnote 1, FPT, PTIME, W[1]-hardness, FPT ≠ W[1], running time N^{(log N)^{1+o(1)}}), p. 7 (encoding length, µ, α), p. 16 (Hom(A), p-Hom(A), core(A)), p. 21 (FPT many-one reductions)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me