Theorem 2, p. 6 — if Pol(A, B) has symmetric polymorphisms of arbitrarily large arities, BLP+Affine correctly solves PCSP-Decision(A, B)
ProvedPCSPBLPAff.Symmetric.theorem_2Let be a promise template over finite domains , , i.e. relational structures of a common signature with a homomorphism . Suppose contains symmetric polymorphisms of arbitrarily large arities: for every there are and a symmetric polymorphism . Then
that is, for every instance : if is satisfiable in , the algorithm accepts ; and if the algorithm accepts , then is satisfiable in .
The algorithm solves the Basic LP, takes a relative interior point, and checks whether the affine relaxation restricted to its support has an integer solution. The theorem shows that one algorithm covers every template with an infinite family of symmetric polymorphisms, without knowing the polymorphisms.
Formalization Note The algorithm is formalized by its acceptance condition (see the definitions module); polynomial running time is not part of the statement. The polymorphism hypothesis depends only on and precedes the quantifier over instances.
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting
namespace PCSPBLPAff.Symmetric
/-- Theorem 2 (arXiv:1907.04383v3, p. 6): if `Pol(𝔸, 𝔹)` has symmetric polymorphisms of
arbitrarily large arities, the BLP+Affine algorithm correctly solves `PCSP-Decision(𝔸, 𝔹)`. -/
theorem theorem_2 {τ : Type} {ar : τ → ℕ} {A B : Type} [Fintype A] [DecidableEq A] [Fintype B]
(𝔸 : RelStruct τ ar A) (𝔹 : RelStruct τ ar B) (hT : IsPromiseTemplate 𝔸 𝔹)
(hsym : ∀ N : ℕ, ∃ L : ℕ, N ≤ L ∧
∃ f : (Fin L → A) → B, IsPolymorphism 𝔸 𝔹 f ∧ IsSymmetric f) :
CorrectlySolves 𝔸 𝔹 := by sorry
end PCSPBLPAff.Symmetric
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.