Preprint
Aug 2026
The Complexity of Boolean Connectivity Problem of $k$-Horn Formulas
The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube. This problem is known to be $\mathsf{coNP}$-complete, even when restricted to $k$-Horn formulas for $k \geq 3$, as shown by Makino, Tamaki, and Yamamoto...
Takashi Horiyama, Shoon Mineyoshi, Yuto Okura et al.
· 0 citations