Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR07-029 | 23rd March 2007 00:00

On the Boolean Connectivity Problem for Horn Relations

RSS-Feed




Revision #1
Authors: Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
Accepted on: 23rd March 2007 00:00
Downloads: 1515
Keywords: 


Abstract:

P. Gopalan, P. G. Kolaitis, E. N. Maneva and C. H. Papadimitriou studied in [Gopalan et al., ICALP2006] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on the
connectivity problems in Schaefer's framework [Schaefer, STOC1978].
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 $\P$.
We disprove their conjecture by showing that there exists a set $S$ of Horn relations such that the connectivity problem for $S$ is $\coNP$-complete.
We also show that the connectivity problem for bijunctive relations can be solved in $O(\min \{n|\gvp|, T(n)\})$ time, where $n$ denotes the number of variables, $\gvp$ 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.


Paper:

TR07-029 | 20th January 2007 00:00

A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem





TR07-029
Authors: Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
Publication: 22nd March 2007 16:58
Downloads: 1385
Keywords: 


Abstract:

P. Gopalan, P. G. Kolaitis, E. N. Maneva and C. H. Papadimitriou
studied in [Gopalan et al., ICALP2006] connectivity properties of the
solution-space of Boolean formulas, and investigated complexity issues
on connectivity problems in Schaefer's framework [Schaefer, STOC1978].
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 P.
We disprove their conjecture by showing that it is coNP-complete for
Horn and dual Horn relations.
This, together with the results in [Gopalan et al., ICALP 2006],implies
a dichotomy theory within Schaefer and a trichotomy theory for the
connectivity problem.
We also show that the connectivity problem for bijunctive relations can
be solved in O(min{n |phi|, T(n)}) time, where n denotes the number of
variables, phi 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.



ISSN 1433-8092 | Imprint