scientific article; zbMATH DE number 1390075
From MaRDI portal
Publication:4934341
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Classical propositional logic (03B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Recommendations
- Constraint satisfaction problems: complexity and algorithms
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Mathematical Foundations of Computer Science 2005
- Computational Complexity of Constraint Satisfaction
- scientific article; zbMATH DE number 140384
- Presenting Constraints
- A Dichotomy Theorem for Typed Constraint Satisfaction Problems
- scientific article; zbMATH DE number 4039349
- Colouring, constraint satisfaction, and complexity
Cited in
(13)- Minimal distance of propositional models
- As Close as It Gets
- Recognizing frozen variables in constraint satisfaction problems
- Satisfiability with index dependency
- Unique perfect phylogeny is NP-hard
- On the unique satisfiability problem
- Isomorphic implication
- On the structure of solution-graphs for Boolean formulas
- On the Boolean connectivity problem for Horn relations
- k-SAT Is No Harder Than Decision-Unique-k-SAT
- scientific article; zbMATH DE number 7561680 (Why is no real title available?)
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Satisfiability with index dependency
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4934341)
