Weak bases of Boolean co-clones
From MaRDI portal
Publication:2448853
DOI10.1016/j.ipl.2014.03.011zbMath1296.68080arXiv1310.3674OpenAlexW2004984049MaRDI QIDQ2448853
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
Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Operations and polynomials in algebraic structures, primal algebras (08A40)
Related Items
Strong partial clones and the time complexity of SAT problems ⋮ Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis ⋮ Weak bases of 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 ⋮ On the interval of strong partial clones of Boolean functions containing \(\mathrm{Pol}(\{(0, 0), (0, 1), (1, 0)\})\) ⋮ Unnamed Item ⋮ As Close as It Gets ⋮ Minimal distance of propositional models ⋮ Best-case and worst-case sparsifiability of Boolean CSPs ⋮ A Dichotomy Theorem for the Inverse Satisfiability Problem
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)
