Partial Polymorphisms and Constraint Satisfaction Problems

DOI10.1007/978-3-540-92800-3_9zbMath1171.68502OpenAlexW2133260738MaRDI 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 complexityconstraint satisfaction problemsclonespartial polymorphisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Operations and polynomials in algebraic structures, primal algebras (08A40) Galois correspondences, closure operators (in relation to ordered sets) (06A15)

Related Items

Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis ⋮ Complexity Classifications for Logic-Based Argumentation ⋮ Unnamed Item ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework ⋮ General lower bounds and improved algorithms for infinite-domain CSPs ⋮ The complexity of problems for quantified constraints ⋮ Weak bases of Boolean co-clones ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight ⋮ Structure identification of Boolean relations and plain bases for co-clones ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ Trichotomies in the complexity of minimal inference ⋮ Unnamed Item ⋮ Unnamed Item ⋮ As Close as It Gets ⋮ Minimal distance of propositional models ⋮ The number of clones determined by disjunctions of unary relations ⋮ Time Complexity of Constraint Satisfaction via Universal Algebra ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ A Dichotomy Theorem for the Inverse Satisfiability Problem

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