0
$\begingroup$

I have spent a lot of time understanding these two issues. If you can help me, please.

  1. Prove that the restriction of SAT to CNF formulas in which each variable xi appears at most twice is solvable in polynomial time.
  2. Prove that the restriction of SAT to CNF formulas in which each variable xi appears at most three times is NP-complete by showing $SAT \leqslant_p SAT_3 $ (hint: find a way to create “clones” of each variable with different names.)

Thanks.

$\endgroup$
3
  • 1
    $\begingroup$ What are your thoughts? $\endgroup$
    – vonbrand
    Mar 11, 2020 at 1:20
  • $\begingroup$ For the first problem I thought of this idea, Consider a variable xi. If it appears once, or if it appears twice but in the same polarity (i.e., both times as a positive literal or both times as a negative literal), then we can set it accordingly and satisfy all the clauses that contain it (more formally, any satisfying assignment can be converted into a satisfying assignment in which xi has this value). $\endgroup$
    – tala
    Mar 11, 2020 at 2:41
  • $\begingroup$ But for the second problem I don't really know how we do it, if you have an idea $\endgroup$
    – tala
    Mar 11, 2020 at 2:43

1 Answer 1

0
$\begingroup$
  1. You can apply Davis-Putnam procedure and note that with the given restriction applying resolution rule will not be increasing formula size exponentially (in fact, it will be decreasing it). Thus, every iteration of procedure will have polynomial time complexity.
  2. Read about Tseytin transformation and try to exploit the same idea. You can replace variable $x$ with $y$ and add $x \leftrightarrow y$ to the formula. With a proper replacement strategy you will be able to obtain an equisatisfiable formula in which every variable occurs at most three times: one in the original formula, one as the left part of equivalence, one as the right one.
$\endgroup$
2
  • $\begingroup$ Thanks for your help ! $\endgroup$
    – tala
    Mar 12, 2020 at 13:14
  • $\begingroup$ I'm doing well with the Davis-puttan procedure. But I didn't quite understand the transformation of tseytin. Can you give an example on a formula $phi$ in CNF please $\endgroup$
    – tala
    Mar 14, 2020 at 14:20

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.