I want to prove that a problem $P_1$ is NP-complete. Let say that I want to do a reduction from SAT problem.

If the instance of problem $P_1$ depends on $M$ and $N$, can I specify the sturcture of the instance of the SAT problem?

More precisely, can I say that, for example, the instance of SAT problem is composed of $M\times N +1$ clauses and every clause has $M+N$ literals ?

Based on this structure of the instance of SAT problem, I construct an instance of $P_1$. Is this proof correct?


In your specific case, what other constraints do you have on $M$ and $N$? For example, if it is possible that $M=N=1$, then each of your clauses will have 2 literals, and your SAT problem actually seems to become the 2-SAT problem which is in P.

So if $P_1$ depends on $M$ and $N$, maybe you should consider an NP-complete SAT variant that somehow takes them into account. In general, if you want to add some additional constraints on SAT (or any other problem you reduce from), make sure the problem still remains NP-complete.

  • $\begingroup$ @np_is_in_p No problem, glad it helps! $\endgroup$ – Juho Feb 28 '14 at 14:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.