Weak bases of Boolean co-clones

DOI10.1016/j.ipl.2014.03.011zbMath1296.68080arXiv1310.3674MaRDI QIDQ2448853

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 complexity; constraint satisfaction problems; clone theory; Boolean relations

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

08A70: Applications of universal algebra in computer science

08A40: Operations and polynomials in algebraic structures, primal algebras

Related Items

Unnamed Item, A Dichotomy Theorem for the Inverse Satisfiability Problem, Strong partial clones and the time complexity of SAT problems, On the interval of strong partial clones of Boolean functions containing \(\mathrm{Pol}(\{(0, 0), (0, 1), (1, 0)\})\), Best-case and worst-case sparsifiability of Boolean CSPs, 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

Cites Work

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