§3.2, proof, p. 14 — if is satisfiable, the LP algorithm reports satisfiable
ProvedSymBoolPCSP.LPRounding.completenesslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1promise-csp
Let be a family of Boolean promise relations and an instance with variables . If is satisfiable, then the LP algorithm of §3.2 outputs "satisfiable": the LP relaxation is feasible and, for every variable ,
This is the completeness half of the algorithm's correctness; it holds without any polymorphism assumption.
Formalization Note " is satisfiable" is SatIn X 𝔸; the algorithm's answer is LPAlgAccepts 𝔸 X from the mission's definition file.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_LPRounding_Basic open PCSPBLPAff.Symmetric
Formal statement
namespace SymBoolPCSP.LPRounding
/-- §3.2, proof, p. 14: if `Ψ_P` is satisfiable then the LP algorithm reports "satisfiable".
A satisfying assignment, read as a 0/1 vector, is an integer LP solution. -/
theorem completeness {τ : Type} {ar : τ → ℕ} (𝔸 : RelStruct τ ar Bool) (X : Instance τ ar)
(hsat : SatIn X 𝔸) : LPAlgAccepts 𝔸 X := by sorry
end SymBoolPCSP.LPRounding
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 14, §3.2, proof (first paragraph)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.