If you want to make money online : Register now

[Solved]: Proving 2P2N SAT is NP-Complete

, , No Comments
Problem Detail: 

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?

Asked By : Alex Chumbley

Answered By : misberner

So here is my take on this. You reduce 3SAT (or SAT, the 3-literal limit does not make anything easier here) to 2P2N in the following way:

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}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21873

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback