Skip to main content
edited tags
Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490
Source Link
tala
  • 95
  • 6

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.