Lemma 7, p. 11 — BLP+Affine correctly solves PCSP-Decision(A, B) iff M_BLP+Aff has a minion homomorphism to Pol(A, B)
ProvedPCSPBLPAff.Characterization.lemma_7affine-relaxationbasic-lpminionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1promise-csp
Let be a promise template on finite domains. The following are equivalent:
- the BLP+Affine algorithm correctly solves (Definition 1);
- admits a minion homomorphism to .
This is the algebraic characterization of the algorithm's power; Lemmas 8 and 9 translate its right-hand side into concrete polymorphisms, giving Theorem 4.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Characterization_Setting
Formal statement
namespace PCSPBLPAff.Characterization
/-- Lemma 7, p. 11: for a promise template `(𝔸, 𝔹)`, BLP+Affine correctly solves
`PCSP-Decision(𝔸, 𝔹)` (Definition 1) iff `M_BLP+Aff` admits a minion homomorphism to
`Pol(𝔸, 𝔹)`. -/
theorem lemma_7 {τ : 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 𝔸 𝔹) :
PCSPBLPAff.Symmetric.CorrectlySolves 𝔸 𝔹 ↔ HasMinionHomToPol 𝔸 𝔹 := by sorry
end PCSPBLPAff.Characterization
Source
arXiv:1907.04383v3, Lemma 7, p. 11 (proof in Appendix A, pp. 13–15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.