Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete

DOI10.1007/978-3-540-74456-6_16zbMATH Open1147.68530OpenAlexW1510911673MaRDI QIDQ3525565FDOQ3525565

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

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)

Mathematics Subject Classification ID

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

Cited In (8)

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

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)