There is a variation of 3CNF-SAT which is called 10-3-CNF-SAT = {<$\Phi$>: $\Phi$ is a satisfiable CNF formula with $\textbf{at most}$ 3 literals per clause and every variable occurs in $\textbf{at most}$ 7 different clauses}. We need to prove that 10-3-CNF-SAT is NP-complete.

My idea is that we can reduce from 3CNF-SAT to 10-3-CNF-SAT. Because 3CNF-SAT is NP-complete, we can get 10-3-CNF-SAT as well. However, I am stuck in the process of proving the mapping reducible relationship between the 3SNF-SAT and 10-3-CNF-SAT.

Does anyone know how to do the reduction part? Thanks in advance.

  • $\begingroup$ Here is an idea. Take any variable that appears in more than 5 clauses, call it $x$. Create another variable $y$ such that $x \iff y$. This would be $(x \land y) \lor (\neg x \land \neg y)$. Then replace $x$ with $y$ in the remaining clauses. Repeat this as necessary. You can see we're basically using $y$ as an alias for $x$. I say "more than 5" because we're having to add 2 clauses, thus putting it at 7 total. $\endgroup$ – ryan Mar 29 '19 at 0:50
  • $\begingroup$ Thanks for the hint. It is really helpful! $\endgroup$ – user4565515 Mar 29 '19 at 1:34
  • $\begingroup$ You could probably reduce this a little bit further too since you can put at most 3 literals in a clause. So if you wanted $z$ and $y$ as an alias for $x$, you could save some extra clauses by doing $$(x \land y \land z) \lor (\neg x \land \neg y \land \neg z)$$ $\endgroup$ – ryan Mar 29 '19 at 4:02

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.