On the Boolean connectivity problem for Horn relations

DOI10.1016/J.DAM.2010.08.019zbMATH Open1214.03027OpenAlexW2162227159MaRDI QIDQ608293FDOQ608293

Suguru Tamaki, Kazuhisa Makino, 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)

Cites Work

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

Cited In (10)

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

   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 👍 👎

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)