scientific article; zbMATH DE number 1390075
From MaRDI portal
Publication:4934341
Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
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
(15)- Complexity of generalized satisfiability counting problems
- Isomorphic implication
- Minimal distance of propositional models
- Satisfiability with index dependency
- As Close as It Gets
- On the structure of solution-graphs for Boolean formulas
- Unique perfect phylogeny is NP-hard
- Satisfiability with index dependency
- On the unique satisfiability problem
- k-SAT Is No Harder Than Decision-Unique-k-SAT
- On the strength of uniqueness quantification in primitive positive formulas
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- On the Boolean connectivity problem for Horn relations
- On the maximum-likelihood decoding problem
- Recognizing frozen variables in constraint satisfaction problems
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)
