# The NP completeness proof for a variation of the 3CNF-SAT problem

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.

• 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. – ryan Mar 29 '19 at 0:50
• Thanks for the hint. It is really helpful! – user4565515 Mar 29 '19 at 1:34
• 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)$$ – ryan Mar 29 '19 at 4:02