On the Boolean connectivity problem for Horn relations

DOI10.1016/J.DAM.2010.08.019MaRDI QIDQ608293zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

Publication date 25 November 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.08.019

zbMATH Keywords

computational complexityBoolean satisfiabilityBoolean connectivityHorn relationsSchaefer's framework

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Classical propositional logic (03B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• On the Boolean Connectivity Problem for Horn Relations
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Solution-Graphs of Boolean Formulas and Isomorphism
• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits

Cites work

• scientific article; zbMATH DE number 1354130 (Why is no real title available?)
• scientific article; zbMATH DE number 861622 (Why is no real title available?)
• scientific article; zbMATH DE number 1390075 (Why is no real title available?)
• A Complete Classification of the Complexity of Propositional Abduction
• A Complexity Index for Satisfiability Problems
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A dichotomy theorem for maximum generalized satisfiability problems.
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of generalized satisfiability counting problems
• Computational aspects of monotone dualization: a brief survey
• Computer Science Logic
• Computing intersections of Horn theories for reasoning with models
• Defaults and relevance in model-based reasoning
• Extended Horn sets in propositional logic
• Horn approximations of empirical data
• On connected Boolean functions
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the solution-space geometry of random constraint satisfaction problems
• Reasoning with models
• Renaming a Set of Clauses as a Horn Set
• Structure identification in relational data
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Inverse Satisfiability Problem
• The approximability of constraint satisfaction problems
• The complexity of minimal satisfiability problems
• The complexity of model checking for circumscriptive formulae
• The complexity of satisfiability problems
• The decision problem for some classes of sentences without quantifiers
• `` Strong NP-Completeness Results

Cited in

(9)

• A reconfigurations analogue of Brooks' theorem and its consequences
• Combinatorial Problems for Horn Clauses
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Approximability of the subset sum reconfiguration problem
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Introduction to reconfiguration
• On the Boolean Connectivity Problem for Horn Relations
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits

This page was built for publication: On the Boolean connectivity problem for Horn relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q608293)