Theorem 4, p. 9 — BLP+Affine solves PCSP(A, B) iff Pol(A, B) has block-symmetric polymorphisms of arbitrarily high width iff (2L+1)-ary ones with blocks L, L+1
ProvedPCSPBLPAff.Characterization.theorem_4affine-relaxationbasic-lpblock-symmetricp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismpromise-csp
Let be a promise template on finite domains , . The following are equivalent:
- the BLP+Affine algorithm correctly solves , i.e. it accepts every instance satisfiable in and rejects every instance unsatisfiable in ;
- has block-symmetric polymorphisms of arbitrarily high width: for every some polymorphism is invariant under permutations within each block of a partition of its coordinates into at least one block, every block having at least elements;
- for every , has a block-symmetric polymorphism of arity with two symmetric blocks of variables of sizes and .
This is the paper's exact characterization of the power of the combined Basic LP and affine relaxation for promise CSPs.
Formalization Note The algorithm is formalized through its acceptance condition (see the definitions file); the polynomial-time claims are not formalized. In item 3 the two blocks are given by a labelling with and .
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Characterization_Setting
Formal statement
namespace PCSPBLPAff.Characterization
/-- Theorem 4, p. 9: for a promise template `(𝔸, 𝔹)` the following are equivalent:
(1) the BLP+Affine algorithm correctly solves `PCSP-Decision(𝔸, 𝔹)`;
(2) `Pol(𝔸, 𝔹)` has block-symmetric polymorphisms of arbitrarily high width;
(3) for every `L ∈ ℕ`, `Pol(𝔸, 𝔹)` has a block-symmetric polymorphism of arity `2L + 1` with
two symmetric blocks of variables of size `L` and `L + 1`. -/
theorem theorem_4 {τ : Type} {ar : τ → ℕ} {A B : Type} [Fintype A] [DecidableEq A] [Fintype B]
(𝔸 : PCSPBLPAff.Symmetric.RelStruct τ ar A) (𝔹 : PCSPBLPAff.Symmetric.RelStruct τ ar B) (hT : PCSPBLPAff.Symmetric.IsPromiseTemplate 𝔸 𝔹) :
List.TFAE
[ PCSPBLPAff.Symmetric.CorrectlySolves 𝔸 𝔹,
∀ N : ℕ, ∃ (L : ℕ) (f : (Fin L → A) → B), PCSPBLPAff.Symmetric.IsPolymorphism 𝔸 𝔹 f ∧ PCSPBLPAff.Symmetric.HasWidthAtLeast f N,
∀ L : ℕ, ∃ f : (Fin (2 * L + 1) → A) → B, PCSPBLPAff.Symmetric.IsPolymorphism 𝔸 𝔹 f ∧
∃ β : Fin (2 * L + 1) → Fin 2,
(Finset.univ.filter (fun l => β l = 0)).card = L ∧
(Finset.univ.filter (fun l => β l = 1)).card = L + 1 ∧
PCSPBLPAff.Symmetric.IsBlockSymmetricFor β f ] := by sorry
end PCSPBLPAff.Characterization
Source
arXiv:1907.04383v3, Theorem 4, p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.