Hypergraph and structure classes, PTIME, FPT, , quasipolynomial time, and the homomorphism problems
DefinitionSparseIncidenceHom_WidthComparison_Supplement_ProblemsClasses. A hypergraph is coded by : vertex set and a list of edges, each a list of vertices. A hypergraph class is a set of codes; a hypergraph belongs to (up to isomorphism) if some code in describes a hypergraph isomorphic to . is recursively enumerable if its set of codes is. has bounded width if , and bounded incidence degeneracy or primal independence if or . A structure class is a set of structure codes; only its well-formed members count (an ill-formed code denotes no structure), and a structure belongs to when it is isomorphic to a well-formed member. The class has bounded incidence degeneracy if , and has bounded width if . The hypergraph size is .
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. : a machine answers within steps. (for a problem with parameter ): a machine started on the pair answers within steps for a computable . is the class of parameterized problems FPT-reducible to -Clique, and means that some problem of is not in . A promise problem is solvable in time if a machine answers every instance correctly and there are and such that on instances of length it halts within
steps.
Problems. : input well-formed structures over the same signature, encoded as the concatenation of their encodings (length ), with ; question . - is the same problem with parameter . and - have the promise and parameter .
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 (resp. ) 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.
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