Restriction of SAT to CNF

Question

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.

Answer 1

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.