Restriction of SAT to CNF

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.

• What are your thoughts? Mar 11, 2020 at 1:20
• 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).
– tala
Mar 11, 2020 at 2:41
• cs.stackexchange.com/q/86730/755
– D.W.
Apr 23 at 18:32

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.
• 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