Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Boolean connectivity:
TR07-029 | 20th January 2007
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint