论文库

原文摘要

We investigate Positive Not-All-Equal 3-Sat under a strong structural restriction and delineate a sharp tractability threshold. In particular, we consider the restriction of Positive Not-All-Equal 3-Sat to instances that simultaneously satisfy the following properties: (i) the clauses can be decomposed into a disjoint union of $k$ partitions of the variable set, and (ii) the collection of clauses is linear, that is, each pair of distinct clauses shares at most one variable. We show that, under these conditions, Positive Not-All-Equal 3-Sat remains NP-complete for any fixed $k \geq 4$. On the positive side, we prove that for $k \leq 3$, the problem is in P and, notably, all such instances are not-all-equal-satisfiable. Our results do not only show robustness of NP-completeness despite the strong structure imposed but also have implications for hypergraph coloring. In particular, by the well-known correspondence between Positive Not-All-Equal 3-Sat and hypergraph coloring, we obtain the following corollary of our results: For $k\geq 4$, Bicolorability is NP-complete for linear 3-uniform $k$-regular hypergraphs even if the edges are given as a decomposition into $k$ perfect matchings; with the same restrictions, for $k \leq 3$ Bicolorability is in P, and all such hypergraphs are bicolorable. In addition, we show that loosening the restriction to 3-clauses by also allowing 2-clauses shifts the above-mentioned tractability threshold. Moreover, we deduce that every instance of Positive Planar Not-All-Equal Sat with at least three distinct variables per clause is nae-satisfiable. Besides, for Linear Not-All-Equal 3-Sat we derive a computational complexity dichotomy with respect to the number of variable appearances.