Weak bases of Boolean co-clones

DOI10.1016/J.IPL.2014.03.011MaRDI QIDQ2448853zbMATH OpenOpenAlexFDO

Authors Victor Lagerkvist

Publication date 5 May 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.3674

zbMATH Keywords

computational complexityconstraint satisfaction problemsclone theoryBoolean relations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70)

Abstract: Universal algebra and clone theory have proven to be a useful tool in the study of constraint satisfaction problems since the complexity, up to logspace reductions, is determined by the set of polymorphisms of the constraint language. For classifications where primitive positive definitions are unsuitable, such as size-preserving reductions, weaker closure operations may be necessary. In this article we consider strong partial clones which can be seen as a more fine-grained framework than Post's lattice where each clone splits into an interval of strong partial clones. We investigate these intervals and give simple relational descriptions, weak bases, of the largest elements. The weak bases have a highly regular form and are in many cases easily relatable to the smallest members in the intervals, which suggests that the lattice of strong partial clones is considerably simpler than the full lattice of partial clones.

Recommendations

• Bases for Boolean co-clones
• C-maximal strong partial clones and the inclusion structure of Boolean weak bases
• On the interval of strong partial clones of Boolean functions containing \(\mathrm{Pol}(\{(0, 0), (0, 1), (1, 0)\})\)
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• Partial Polymorphisms and Constraint Satisfaction Problems

Cites work

• Bases for Boolean co-clones
• Closed systems of functions and predicates
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• Function Algebras on Finite Sets
• On some closed classes in partial two-valued logic
• On the algebraic structure of combinatorial problems
• Partial Polymorphisms and Constraint Satisfaction Problems
• Structure identification of Boolean relations and plain bases for co-clones
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The algebras of partial functions and their invariants
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Weak bases of Boolean co-clones

Cited in

(14)

• Minimal distance of propositional models
• Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
• As Close as It Gets
• Weak bases of Boolean co-clones
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Bases for Boolean co-clones
• C-maximal strong partial clones and the inclusion structure of Boolean weak bases
• Structure identification of Boolean relations and plain bases for co-clones
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• A dichotomy theorem for the inverse satisfiability problem
• Strong partial clones and the time complexity of SAT problems
• Best-case and worst-case sparsifiability of Boolean CSPs
• scientific article; zbMATH DE number 7561680 (Why is no real title available?)
• On the interval of strong partial clones of Boolean functions containing \(\mathrm{Pol}(\{(0, 0), (0, 1), (1, 0)\})\)

This page was built for publication: Weak bases of Boolean co-clones

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2448853)