The Complexity of Boolean Connectivity Problem of $k$-Horn Formulas

Takashi Horiyama, Shoon Mineyoshi, Yuto Okura +2

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…