Partial Polymorphisms and Constraint Satisfaction Problems
From MaRDI portal
Publication:5504705
DOI10.1007/978-3-540-92800-3_9zbMath1171.68502MaRDI QIDQ5504705
Publication date: 22 January 2009
Published in: Complexity of Constraints (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92800-3_9
68Q25: Analysis of algorithms and problem complexity
08A70: Applications of universal algebra in computer science
08A40: Operations and polynomials in algebraic structures, primal algebras
06A15: Galois correspondences, closure operators (in relation to ordered sets)
Related Items
Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Structure identification of Boolean relations and plain bases for co-clones, The complexity of problems for quantified constraints, Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight, Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
Cites Work
- Unnamed Item
- Structure identification of Boolean relations and plain bases for co-clones
- Bases for Boolean co-clones
- On the algebraic structure of combinatorial problems
- Complexity of constraints. An overview of current research themes
- Closed systems of functions and predicates
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Enumerating All Solutions for Constraint Satisfaction Problems
- On some closed classes in partial two-valued logic
- The algebras of partial functions and their invariants
- On the Structure of Polynomial Time Reducibility
- On generating all solutions of generalized satisfiability problems
- Function Algebras on Finite Sets
- The complexity of satisfiability problems
- Mathematical Foundations of Computer Science 2005