1
$\begingroup$

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?

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

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

$\endgroup$
0
$\begingroup$

Might have gotten this wrong, in the end, but here's my attempt.

Proving it's NP-complete is a two step process: 1) Prove it's in NP (obvious, it's an SAT problem) 2) Prove it's NP-hard by reducing it to 3SAT

Think about a given 3SAT problem, we'll assume it has literals that appear more than twice (otherwise what's the point). For any literal that appears too often, we just swap out a new variable with an identical Truth mapping to it and its compliment. Do this for every variable until all literals only appear at most twice. It is just as hard to solve as 3SAT at that point.

$\endgroup$
  • 1
    $\begingroup$ I doubt that this would work. First, you cannot prove NP-completeness by reducing 2P2N to 3SAT - you have to do it the other way round (which you do correctly in your description). Furthermore, you cannot add variables with "an identical truth mapping" just like that, as SAT is finding such a truth mapping (among ALL possible). You could encode this in additional clauses, but this requires great care to ensure that with your new clauses you do not violate the 2P2N restriction. $\endgroup$ – misberner Feb 21 '14 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.