0
$\begingroup$

Also, what's the difference between transforming a problem into another problem and doing a reduction? They sound synonymous to me. Thank you!

$\endgroup$
  • 1
    $\begingroup$ Please avoid asking multiple distinct questions at once. $\endgroup$ – xskxzr May 31 '18 at 3:28
0
$\begingroup$

To prove that a problem is NP-complete, you need to show two things:

  1. The problem is NP-hard, i.e. it's at least as hard as any problem in NP
  2. The problem is in NP, i.e. it's no harder than NP

Doing a reduction both ways is the easiest way to do this: reducing something in NP to a new problem shows that the new problem is NP-hard, and reducing your new problem to something in NP shows that the new problem is no harder than NP.

I've never heard "transforming" used formally, but I would guess from context it's the same as doing a polynomial-time reduction.

$\endgroup$
  • $\begingroup$ Does showing that a problem A can be verified in polynomial time and showing an unknown problem A is reducible to a known NPC problem B accomplish the same thing? $\endgroup$ – notorious May 31 '18 at 2:32
  • $\begingroup$ It does not. Suppose A is in P. Then A can be verified in poly time (by solving it) and A can be reduced to B in poly time (by solving A in poly time, then running B and ignoring the answer) but that doesn't make A NP-complete. $\endgroup$ – Draconis May 31 '18 at 2:57

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.