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.
