# Proving 2P2N SAT is NP-Complete

I hope I named this CNF Boolean sentence the correct way. The way I see it, a 2P2N is where each literal appears twice (or at most twice, but we can say twice without loss of generality).

I am trying to prove it is Satisfiable. How do I do this? Do I need to try to reduce it to 3-SAT (might need some help doing that as well). Or is there another method of proving satisfiability?

• What do you mean by "I am trying to prove it is Satisfiable"? When is a language Satisfiable? – Yuval Filmus Feb 21 '14 at 3:32
• In this case you should probably reduce 3SAT to 2P2N-SAT to show that the latter is NP-hard. – Yuval Filmus Feb 21 '14 at 3:36
• @YuvalFilmus, good call, that worked out great! – Alex Chumbley Feb 21 '14 at 4:58
• Perhaps you could answer your own question, for the record? – Yuval Filmus Feb 21 '14 at 5:17

As noted above, you cannot easily add variables with an enforced equivalent truth mapping as existing ones (specifying $x \Leftrightarrow y$ in CNF requires 1 positive any 1 negative literal of each $x$ and $y$, so you cannot extend this to an arbitrary number of "copies"). At least not directly: $(x \Leftrightarrow y) \wedge (y \Leftrightarrow z) \wedge (z \Leftrightarrow w)$ will leave you with no free literals for $y$ and $z$. However, an equivalent to the above is $(x \Rightarrow y) \wedge (y \Rightarrow z) \wedge (z \Rightarrow w) \wedge (w \Rightarrow x)$ (note that $x \Rightarrow y \equiv \overline{x} \vee y$). Hence, this "chain" requires you to use up your two positive, two negative literals for your existing variable $x$, but leaves you with one free negative respectively positive literals for each of $y$, $z$ and $w$. These you can use to replace any occurences of $x$ or $\overline{x}$.