The Curse and Blessing of Not-All-Equal in k-Satisfiability

S. Cliff Liu

As a natural variant of the $k$-SAT problem, NAE-$k$-SAT additionally requires the literals in each clause to take not-all-equal (NAE) truth values. In this paper, we study the wor…