Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/437310015234641921
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link

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?