Partial Polymorphisms and Constraint Satisfaction Problems

DOI10.1007/978-3-540-92800-3_9zbMath1171.68502MaRDI QIDQ5504705

Henning Schnoor, Ilka Schnoor

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

zbMATH Keywords

computational complexity; constraint satisfaction problems; clones; partial polymorphisms

Mathematics Subject Classification ID

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, 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