Is (3,3)-NAE-SAT NP-complete?

245 Views Asked by At

In this question I assume the following: in either $(i,j)$-SAT or $(i,j)$-NAE-SAT, every clause has exactly $i$ literals, and a given variable appears at most $j$ times in the entire formula. NAE means Not-All-Equal, i.e. we want not only to satisfy the formula, but each clause must have at least one literal true and at least one literal false in that assignment.

I know that $(3,4)$-SAT and $(3,4)$-NAE-SAT are NP-complete. I also know that $(3,3)$-SAT is trivial (from this paper). But is there a result for $(3,3)$-NAE-SAT?