Weak bases of Boolean co-clones

DOI10.1016/J.IPL.2014.03.011zbMATH Open1296.68080arXiv1310.3674OpenAlexW2004984049MaRDI QIDQ2448853FDOQ2448853

Authors: Victor Lagerkvist 

Publication date: 5 May 2014

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

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.

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

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

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)

Cites Work

• Function Algebras on Finite Sets
• On the algebraic structure of combinatorial problems
• The algebras of partial functions and their invariants
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• Closed systems of functions and predicates
• On some closed classes in partial two-valued logic
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Structure identification of Boolean relations and plain bases for co-clones
• Weak bases of Boolean co-clones
• Partial Polymorphisms and Constraint Satisfaction Problems
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Bases for 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
• C-maximal strong partial clones and the inclusion structure of Boolean weak bases
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Bases for Boolean co-clones
• 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
• Title not available (Why is that?)
• 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)