5
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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