Symmetric promise constraint satisfaction problems: beyond the Boolean case

DOI10.4230/LIPICS.STACS.2021.10MaRDI QIDQ7231533zbMATH OpenFDO

Authors Libor Barto, Diego Battistelli, Kevin M. Berg

Publication date 21 April 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2021.10

zbMATH Keywords

Boolean PCSPconstraint satisfaction problemspolymorphismpromise constraint satisfaction

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• (2+)-Sat is NP-hard
• A dichotomy theorem for nonuniform CSPs
• A proof of the CSP dichotomy conjecture
• Algebraic approach to promise constraint satisfaction
• Classifying the Complexity of Constraints Using Finite Algebras
• Dichotomy for symmetric Boolean PCSPs
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
• The complexity of 3-colouring \(\mathbf{H}\)-colourable graphs
• The complexity of promise SAT on non-Boolean domains
• The complexity of satisfiability problems
• The hardness of 3-uniform hypergraph coloring
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• The wonderland of reflections

Cited in

(3)

• Beyond PCSP (1-in-3, NAE)
• Improved linearly ordered colorings of hypergraphs via SDP rounding
• Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs

This page was built for publication: Symmetric promise constraint satisfaction problems: beyond the Boolean case

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