Sandwiches for promise constraint satisfaction

DOI10.1007/S00012-020-00702-5MaRDI QIDQ1996093zbMATH OpenOpenAlexFDO

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

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

affine structureconstraint satisfactionpolymorphismpromise problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7724184
• Algebraic approach to promise constraint satisfaction
• Algebraic Approach to Promise Constraint Satisfaction
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Algebraic theory of promise constraint satisfaction problems, first steps
• Complexity issues for the sandwich homogeneous set problem
• Constraint Satisfaction
• Sandwich and probe problems for excluding paths
• scientific article; zbMATH DE number 769502

Cites work

• A proof of the CSP dichotomy conjecture
• Algebraic approach to promise constraint satisfaction
• An algorithmic blend of LPs and ring equations for promise CSPs
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
• The complexity of satisfiability problems
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems

Cited in

(2)

• Small Promise CSPs that reduce to large CSPs
• Three fundamental questions in modern infinite-domain constraint satisfaction

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1996093)