Sandwiches for promise constraint satisfaction

DOI10.1007/s00012-020-00702-5OpenAlexW3122635138MaRDI QIDQ1996093

Athena Sparks, Poramate Nakkirt, Peter Mayr, Trevor Manders, Guofeng Deng, Ezzeddine El Sai

Publication date: 3 March 2021

Published in: Algebra Universalis (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.07487

zbMATH Keywords

polymorphismconstraint satisfactionaffine structurepromise problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Small Promise CSPs that reduce to large CSPs

Cites Work

• A Proof of the CSP Dichotomy Conjecture
• The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems
• Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
• Algebraic approach to promise constraint satisfaction
• An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
• The complexity of satisfiability problems
• Unnamed Item

This page was built for publication: Sandwiches for promise constraint satisfaction