Taking an NP-complete problem like vertex cover if we can find a reduction which is exponential and not polynomial and the reduction we do to a problem can be solved in polynomial time, then what would be it's implications?

Based on Yuval's answer, I wanted to throw this scenario into the place also.

If we have a problem in P which we can reduce in polynomial time to an NP-complete problem for e.g vertex cover, what happens then?


1 Answer 1


There would be no implications, and indeed I will now exhibit just such a reduction. The reduction takes an instance of vertex cover, finds the optimal value (in exponential time), and then reduces it to the language $\{0\} \in P$ (the language consisting of the single string $0$), by outputting $0$ if there is a vertex cover below the required threshold, $1$ otherwise.

  • $\begingroup$ What do you think about the reverse ? $\endgroup$
    – gizgok
    Nov 20, 2012 at 15:17
  • 3
    $\begingroup$ By the definition of NP-completeness, there is a polytime reduction from any language in NP to any NP-complete language. $\endgroup$ Nov 20, 2012 at 17:34

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.