Advertisement
Published in:
2007 | OriginalPaper | Chapter
On the Boolean Connectivity Problem for Horn Relations
Authors : Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
Published in: Theory and Applications of Satisfiability Testing – SAT 2007
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Gopalan et al. studied in ICALP06 [17] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on the connectivity problems in Schaefer’s framework. A set
S
of logical relations is
Schaefer
if all relations in
S
are either bijunctive, Horn, dual Horn, or affine. They conjectured that the connectivity problem for
Schaefer
is in
$\mathcal{P}$
. We disprove their conjecture by showing that there exists a set
S
of Horn relations such that the connectivity problem for
S
is co
$\mathcal{NP}$
-complete. We also show that the connectivity problem for bijunctive relations can be solved in
O
( min {
n
|
ϕ
|,
T
(
n
)}) time, where
n
denotes the number of variables,
ϕ
denotes the corresponding 2-CNF formula, and
T
(
n
) denotes the time needed to compute the transitive closure of a directed graph of
n
vertices. Furthermore, we investigate a tractable aspect of Horn and dual Horn relations with respect to characteristic sets.