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

Boolean relationsclone theorycomputational complexityconstraint satisfaction problems

Mathematics Subject Classification ID

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

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 algebras of partial functions and their invariants
• The complexity of satisfiability problems: Refining Schaefer's theorem
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Weak bases of Boolean co-clones

Cited in

(14)

• Bases for Boolean co-clones
• 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
• Minimal distance of propositional models
• Weak bases of Boolean co-clones
• As Close as It Gets
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• Strong partial clones and the time complexity of SAT problems
• On the strength of uniqueness quantification in primitive positive formulas
• On the interval of strong partial clones of Boolean functions containing \(\mathrm{Pol}(\{(0, 0), (0, 1), (1, 0)\})\)
• A dichotomy theorem for the inverse satisfiability problem
• C-maximal strong partial clones and the inclusion structure of Boolean weak bases
• Best-case and worst-case sparsifiability of Boolean CSPs
• Structure identification of Boolean relations and plain bases for co-clones

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)