Assuming 3-OCC-MAX SAT is the language of all CNF formulas in which every variable appears in at most 3 clauses. Is this problem NP-Complete? I'm trying to find a karp reduction between SAT and this problem, but I couldn't find it.

  • 1
    $\begingroup$ Look for a gadget that allows you to "copy" a variable. $\endgroup$ Oct 16, 2020 at 22:27
  • $\begingroup$ Which direction causes you trouble? $\endgroup$
    – greybeard
    Oct 16, 2020 at 23:30


Your Answer

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

Browse other questions tagged or ask your own question.