Bases for Boolean co-clones
From MaRDI portal
Publication:1044708
DOI10.1016/J.IPL.2005.06.003zbMath1184.68351OpenAlexW2035877205MaRDI QIDQ1044708
Henning Schnoor, Elmar Böhler, Heribert Vollmer, Steffen Reith
Publication date: 18 December 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2005.06.003
Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (22)
What makes propositional abduction tractable ⋮ Complexity Classifications for Logic-Based Argumentation ⋮ Lewis dichotomies in many-valued logics ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework ⋮ Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems ⋮ The complexity of problems for quantified constraints ⋮ Weak bases of Boolean co-clones ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ On Boolean primitive positive clones ⋮ Structure identification of Boolean relations and plain bases for co-clones ⋮ The expressive power of valued constraints: Hierarchies and collapses ⋮ Trichotomies in the complexity of minimal inference ⋮ The Next Whisky Bar ⋮ An approximation trichotomy for Boolean \#CSP ⋮ Unnamed Item ⋮ The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis ⋮ As Close as It Gets ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ Minimal distance of propositional models ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ Partial Polymorphisms and Constraint Satisfaction Problems
Cites Work
This page was built for publication: Bases for Boolean co-clones
