§3.2 — the LP algorithm decides PCSP(Γ) when or for all odd
ProvedSymBoolPCSP.LPRounding.algorithm_3_2_correctLet be a finite family of Boolean promise relations, , and suppose that
- is a polymorphism of for every odd , or
- is a polymorphism of for every odd .
Then the LP algorithm of §3.2 decides : for every instance ,
Equivalently, it answers "satisfiable" on every YES instance and "unsatisfiable" on every NO instance. No symmetry of the relations is assumed.
This is the algebraic content of the Majority and Alternating-Threshold cases of Theorem 3.2: since the LP has size linear in the instance and LPs are solvable in polynomial time, it yields polynomial-time tractability of .
Formalization Note The algorithm's answer is LPAlgAccepts 𝔸 X (an LP feasibility test over , see the definition file). The hypothesis is a disjunction of two universal statements, not "for every odd , or ". The polynomial running time, and hence the printed conclusion "PCSP(Γ) is polynomial-time tractable", is not formalized.
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_LPRounding_Basic open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.LPRounding
/-- §3.2, pp. 13–15 (algebraic core of the Majority and Alternating-Threshold cases of
Theorem 3.2, p. 15): let `Γ` be a finite family of Boolean promise relations such that `Maj_L` is a
polymorphism of `Γ` for every odd `L`, or `AT_L` is a polymorphism of `Γ` for every odd `L`. Then
the LP algorithm of §3.2 decides `PCSP(Γ)`: it reports "satisfiable" on every instance with
`Ψ_P` satisfiable, and whenever it reports "satisfiable", `Ψ_Q` is satisfiable. -/
theorem algorithm_3_2_correct {τ : Type} [Fintype τ] {ar : τ → ℕ} (𝔸 𝔹 : RelStruct τ ar Bool)
(hPQ : ∀ R, 𝔸.rel R ⊆ 𝔹.rel R)
(hpol : (∀ L : ℕ, Odd L → IsPolymorphism 𝔸 𝔹 (SymBoolPCSP.CFixing.Maj L)) ∨
(∀ L : ℕ, Odd L → IsPolymorphism 𝔸 𝔹 (SymBoolPCSP.CFixing.AT L))) :
∀ X : Instance τ ar,
(SatIn X 𝔸 → LPAlgAccepts 𝔸 X) ∧ (LPAlgAccepts 𝔸 X → SatIn X 𝔹) := by sorry
end SymBoolPCSP.LPRounding
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.