principleMinor
What would an exponential reduction from an NP-complete problem to P signify?
Viewed 0 times
problemwhatexponentialwouldcompletereductionfromsignify
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#6785, answer score: 6
Revisions (0)
No revisions yet.