# Reduction of $3SAT$ to $2P2N-3SAT$ (without trivial clauses)

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.