On the Boolean connectivity problem for Horn relations

Gopalan et al. studied in [P. Gopalan, P.G. Kolaitis, E.N. Maneva, C.H. Papadimitriou, The connectivity of Boolean satisfiability: computational and structural dichotomies, in: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, 2006, pp. 346–357] and [P. Gopalan, P.G. Kolaitis, E.N. Maneva, C.H. Papadimitriou, The connectivity of Boolean satisfiability: computational and structural dichotomies, SIAM J. Comput. 38 (6) (2009) 2330–2355] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on the connectivity problems in Schaefer’s framework. A set SS of logical relations is Schaefer if all relations in SS are either bijunctive, Horn, dual Horn, or affine. They first conjectured that the connectivity problem for Schaefer is in PP. We disprove their conjecture by showing that there exists a set SS of Horn relations such that the connectivity problem for SS is coNP-complete. We also investigate a tractable aspect of Horn and dual Horn relations with respect to characteristic sets.