Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
What do you think about the reverse ? – gizgok Nov 20 '12 at 15:17
By the definition of NP-completeness, there is a polytime reduction from any language in NP to any NP-complete language. – Yuval Filmus Nov 20 '12 at 17:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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