arXiv:2610.02565
The complexity of entangled graph colouring via polymorphisms
Eric Culf
Abstract
Constraint satisfaction problems (CSPs) with operator assignments to the variables provide a well-structured setting to study the decision complexity of the entangled value of classes of nonlocal games. Due to the CSP dichotomy theorem, the complexity of constraint satisfaction problems with classical assignments can be fully understood by studying the symmetries of the CSP, in terms of the polymorphisms of the underlying relational structure. In this work, we show that the polymorphism-based reductions between CSPs can be generalised to gap-preserving reductions between entangled CSPs based on an entangled analogue of the polymorphisms. This reduction allows us to show undecidability of entangled graph colouring with more than three colours, a problem that has proved resistant to prior hardness reductions based on commutativity gadgets.
AI Summary
The paper asks when algebraic reductions between classical constraint satisfaction problems (CSPs) extend to entangled CSPs while preserving a constant completeness–soundness gap. The motivating case is non-oracular entangled graph colouring with $n\geq4$ colours, where commutativity gadgets are unavailable. It introduces stable minion homomorphisms between approximate entangled polymorphisms and proves that their existence yields polynomial-time reductions preserving perfect completeness and some constant soundness gap: for every source soundness $s<1$, the target has soundness $s'<1$. The reductions can map oracular CSPs to either oracular or non-oracular CSPs. A dual algebraic framework, called cominions, supplies a sufficient construction criterion; the stability argument uses finite-order-unitary rounding and sum-of-squares estimates. Applying the framework gives constant-gap $\mathrm{RE}$-completeness of non-oracular quantum $n$-colouring for every fixed $n\geq3$, extending the previously known $n=3$ case. The explicitly stated succinct-game corollary also gives $\mathrm{coRE}$-completeness in the commuting-operator model. The colouring construction uses central projections in quantum polymorphism algebras to map into the projection-only polymorphisms of 3SAT. Further applications establish hardness for homomorphism to the diamond graph and gap-preserving equivalence between constraint-variable and constraint-constraint presentations. The framework gives sufficient reduction criteria, not a complexity dichotomy or a necessary characterization. Extension to polynomial-time reductions for succinct instances assumes a well-connected source template, and no explicit numerical soundness gap is supplied. Related work already obtains colouring hardness through a simpler direct reduction; the distinction here is the polymorphism-based reduction framework.
Error found: The final parameter choice for stability property (ii) in Section 3.4 yields a defect bound of 5ε/3, not ε; dividing δ by 9 fixes it. The monomial telescoping bound in Section 3.4 omits necessary operator-norm factors for the unrounded images φ(Vₙ,ₖ), which are not assumed to be contractions. The soundness estimate in Section 4.2 uses the constraint count of A^(R^B) to normalize a defect on B^(R^B), where the latter structure's constraint count is required.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 33 pages, 0 figures