On the Boolean connectivity problem for Horn relations

DOI10.1016/j.dam.2010.08.019zbMath1214.03027OpenAlexW2162227159MaRDI QIDQ608293

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) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

An exact algorithm for the Boolean connectivity problem for \(k\)-CNF ⋮ Approximability of the subset sum reconfiguration problem ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Introduction to reconfiguration

Cites Work

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

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