HiveBrain v1.2.0
Get Started
← Back to all entries
principleMinor

What would an exponential reduction from an NP-complete problem to P signify?

Submitted by: @import:stackexchange-cs··
0
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?

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.