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?
