Structure identification of Boolean relations and plain bases for co-clones

DOI10.1016/j.jcss.2008.02.005zbMath1152.68020OpenAlexW2028127968MaRDI QIDQ955340

Nadia Creignou, Bruno Zanuttini, Phokion G. Kolaitis

Publication date: 19 November 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2008.02.005

zbMATH Keywords

computational complexityclosure propertiesBoolean co-clonesBoolean constraintsinverse satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Boolean functions (06E30)

Related Items (22)

The complexity of counting locally maximal satisfying assignments of Boolean CSPs ⋮ What makes propositional abduction tractable ⋮ The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs ⋮ The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ Complexity Classifications for Logic-Based Argumentation ⋮ Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems ⋮ Weak bases of Boolean co-clones ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem ⋮ Counting Constraint Satisfaction Problems. ⋮ Boolean max-co-clones ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ An approximation trichotomy for Boolean \#CSP ⋮ Unnamed Item ⋮ Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems ⋮ Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin ⋮ Minimal distance of propositional models ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ Partial Polymorphisms and Constraint Satisfaction Problems ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ A Dichotomy Theorem for the Inverse Satisfiability Problem ⋮ Dichotomy on intervals of strong partial Boolean clones

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bases for Boolean co-clones
• Structure identification in relational data
• Closed systems of functions and predicates
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• On the Structure of Polynomial Time Reducibility
• The Inverse Satisfiability Problem
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• The complexity of satisfiability problems
• Partial Polymorphisms and Constraint Satisfaction Problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: Structure identification of Boolean relations and plain bases for co-clones