Given an instance of $3SAT$ the objective is to reduce it directly to $2P2N-3SAT$ without the reduction having any 'trivial' clauses. The trivial clauses can be where the same variable in a clause is used twice as follows: $x+\overline{x}+y=1$ or $x+x+y=1$. Both these clauses are trivial since the first is trivially TRUE and the second is obviously the 2 literal clause $x+y=1$.

The problem is $NPC$ but I am unable to find a complete reduction to it in any place.

The way I am approaching is as follows:

For each variable $(x)$, that occurs more that $4$ times as a literal, let the number of times it appears as positive and negative literal be $P_x$ and $N_x$ respectively. Assuming $P_x > N_x$ create $P_x-2$ new variables $a_0, a_1, a_2...a_{P_x-2}$. Now add clauses: $\overline{x}+a_0=1;\overline{a_0}+a_1=1; \overline{a_1}+a_2=1;....;\overline{a_{P_x-2}}+x=1$

This ensures that $x=a_0=a_1=...=a_{P_x-2}$. Now, we replace the third occurrence of $x$ and $\overline{x}$ with $a_0$ and $\overline{a_0}$ respectively, fourth with and $a_1$ and $\overline{a_1}$ so on.

Thus, we have ensured each literal occurs either once or twice. But we are still left with clauses of length 2, and we haven't yet enforced $2P2N$ constraint (with non trivial clauses). I am a bit lost how to proceed further.

Can someone please help with the complete reduction?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.