Observation 15, pp. 14–15 — BLP+Affine correctly solves PCSP(A, B) iff X → F_{M_BLP+Aff}(A) implies X → B
ProvedPCSPBLPAff.Characterization.observation_15affine-relaxationbasic-lpfree-structurep2o-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 ;
- for every instance , if is satisfiable in the free structure then is satisfiable in :
This restates Definition 1 through the free structure; it is the first step of the proof of Lemma 7 in Appendix A.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Characterization_Setting
Formal statement
namespace PCSPBLPAff.Characterization
/-- Observation 15, pp. 14–15: for a promise template `(𝔸, 𝔹)`, BLP+Affine correctly solves
`PCSP-Decision(𝔸, 𝔹)` iff every instance satisfiable in the free structure
`F_{M_BLP+Aff}(𝔸)` is satisfiable in `𝔹`. -/
theorem observation_15 {τ : 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 𝔸 𝔹 ↔ ∀ X : PCSPBLPAff.Symmetric.Instance τ ar, PCSPBLPAff.Symmetric.SatIn X (freeStruct 𝔸) → PCSPBLPAff.Symmetric.SatIn X 𝔹 := by sorry
end PCSPBLPAff.Characterization
Source
arXiv:1907.04383v3, Observation 15, pp. 14–15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.