Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete

DOI10.1007/978-3-540-74456-6_16MaRDI QIDQ3525565zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, Mark Siggers

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74456-6_16

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27)

Recommendations

• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• A proof of the CSP dichotomy conjecture
• scientific article; zbMATH DE number 1670830
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Forbidden lifts (NP and CSP for combinatorialists)

Cited in

(8)

• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• Characterizations of several Maltsev conditions.
• Forbidden lifts (NP and CSP for combinatorialists)
• NP for Combinatorialists
• Colouring, constraint satisfaction, and complexity
• Easy NP-hardness Proofs of Some Subset Choice Problems
• Sublinear P system solutions to NP-complete problems
• \(H\)-coloring degree-bounded (acyclic) digraphs

This page was built for publication: Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete

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