Problem Detail: 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.
Asked By : Juho
Answered By : Xavier Labouze
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 : $(xlor y lor lnot y)$ and $(lnot x lor ylor 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.
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 : $(xlor y lor lnot y)$ and $(lnot x lor ylor 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16817
