On the Boolean Connectivity Problem for Horn Relations

DOI10.1007/978-3-540-72788-0_20zbMath1214.03026OpenAlexW1741233485MaRDI QIDQ3612466

Kazuhisa Makino, Masaki Yamamoto, Suguru Tamaki

Publication date: 10 March 2009

Published in: Theory and Applications of Satisfiability Testing – SAT 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-72788-0_20

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) Connectivity (05C40)

Related Items (2)

The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

This page was built for publication: On the Boolean Connectivity Problem for Horn Relations