Consider the following 3-SAT variant defined over the variables $x_1,\ldots,x_n$. In the $k$P$k$N-3SAT problem each variable $x_j$, $j \in [n]$, occurs exactly $k$ times as a positive literal in $\phi$, and exactly $k$ times as a negative literal in $\phi$, where $\phi$ is a 3-CNF formula. The problem is then to decide if such a formula has a satisfying assignment.

Is the $k$P$k$N-3SAT problem NP-complete?

In the $m$P$n$N-SAT problem each positive literal occurs exactly $m$ times in $\phi$, and each negative literal occurs exactly $m$ times in $\phi$, where $\phi$ is a CNF formula. It was shown in [1] that $2$P$1$N-SAT is NP-complete. This hints that the $k$P$k$N-3SAT problem is hard as well.

The $1$P$1$N-SAT is apparently easy, see a related question and answer here. Is $k$P$k$N-3SAT perhaps hard already for $k \geq 2$?

[1] Yoshinaka, Ryo. "Higher-order matching in the linear lambda calculus in the absence of constants is NP-complete." Term Rewriting and Applications. Springer Berlin Heidelberg, 2005. 235-249.


1) 2P2N-3SAT is NP-complete

(Edit to take into account all comments below)

Take a 2P1N-SAT instance, check the all-1 vector is not a model, then add the clause with all variables negated to the formula to transform it into a 2P2N-SAT instance.

For each 1-clause $(a)$ in the new 2P2N formula, replace it by the three following 3-clauses : $(a \lor x \lor x)(\lnot x \lor y \lor y)(\lnot x \lor \lnot y \lor \lnot y)$ where $x,y$ are fresh 2P2N variables (i.e. appearing twice as positive literals and twice as negative literals).
For each 2-clause $(a \lor b)$ in the formula, replace it by the six following 3-clauses : $(a \lor b \lor x)(\lnot x \lor y \lor y)(\lnot x \lor \lnot y \lor \lnot y)(x \lor z \lor \lnot z)(z \lor t \lor \lnot t)(\lnot z \lor t \lor \lnot t)$ where $x,y,z,t$ are fresh 2P2N variables.
Keep all 3-clauses in the formula.
For each $k$-clause ($k>3$) in the formula, transform it into a set of 3-clauses by the usual way, which does not change the number of occurences of positive (negative) literals of the taken $k$-clause, but add only extra variables which appear once as a positive literal and once as a negative literal. For each such new variable $x$, add the two following clauses to the 3-CNF formula : $(x\lor y \lor \lnot y)$ and $(\lnot x \lor \ y\lor \lnot y)$ where $y$ is a fresh 2P2N variable.

All these transformations can obviously be done in polynomial time and transform the 2P1N-SAT instance into a 2P2N-3SAT instance. The NP-complete 2P1N-SAT problem is then reducible to the 2P2N-3SAT problem.

2) The extension to $k$P$k$N-3SAT can be done in the same spirit (a bit longer) to prove it is NP-complete as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.