1
$\begingroup$

I'm taking an algorithms course in which we are discussing proofs that problems are NP-Complete.

Our proofs usually take the form:

Given a problem $\Pi$,
1. Prove that $\Pi$ is NP.
2. Select an NP-C problem $\Pi'$.
3. Find a transformation $\propto$ from $\Pi'$ to $\Pi$.
4. Prove that $\propto$ is polynomial.
5. Prove that iff a solution $S$ to $\Pi'$ is correct, then $\propto(S)$ is a solution to $\Pi$.

I have a question about step $2$. When I'm attempting to prove that a problem $\Pi$ is NP-C, how do I go about selecting $\Pi'$? Is there a systematic approach I can use? If not, what is the intuition behind selecting $\Pi'$, and how can I practice and develop that intuition?

$\endgroup$
  • $\begingroup$ The dumb answer is, any $\Pi' \in \mathsf{NPC}$ works. So you are probably asking, is there a strategy for picking "good" reduction partners? None that I know of. This might be a duplicate of our reference question. Oh wait, I found a better one. $\endgroup$ – Raphael Sep 23 '14 at 21:07
  • $\begingroup$ You a quite right. The Finding Reductions question was exactly what I was asking for. Should I delete this duplicate? $\endgroup$ – Kevin Sep 23 '14 at 21:30
  • $\begingroup$ (Also, thank you for finding answer for me!) $\endgroup$ – Kevin Sep 23 '14 at 21:34
  • $\begingroup$ You are welcome, that's what we're here for. :) We tend to leave duplicates around (if they are not verbatim copies) in the hope that more searches are sucessful. $\endgroup$ – Raphael Sep 24 '14 at 7:16