Boolean max-co-clones

DOI10.1007/s00012-015-0336-1zbMath1348.08004MaRDI QIDQ494629

Andrei A. Bulatov

Publication date: 1 September 2015

Published in: Algebra Universalis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00012-015-0336-1

zbMATH Keywords

approximate counting; Boolean max-co-clones; max-co-clones

Mathematics Subject Classification ID

08A70: Applications of universal algebra in computer science

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

06B99: Lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of constraint satisfaction games and QCSP
• Structure identification of Boolean relations and plain bases for co-clones
• An approximation trichotomy for Boolean \#CSP
• The relative complexity of approximate counting problems
• Closed systems of functions and predicates
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Constraint Satisfaction with Counting Quantifiers
• An inequality for the weights of two families of sets, their unions and intersections
• Closure properties of constraints
• The expressibility of functions on the boolean domain, with applications to counting CSPs
• The complexity of the counting constraint satisfaction problem
• The complexity of satisfiability problems
• Basics of Galois Connections
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)