CODEWITHSUNDEEP
complexity-theorynp
marc
marc

Reputation: 101

polynomial time reduction from a problem to a NP-complete problem

I have problems to solve the following question: If there are two problems p1 and p2, p2 is NP-complete and there is a polynomial reduction from p1 to p2, then p1 ...
a) is NP-hard but not necessarily NP-complete
b) could be in P, even if P!=NP
c) is NP-complete
d) none of the above
I think c) is correct, but I am not sure and how can I justify ist?

Upvotes: -1

Views: 687

Answers (1)

Berthur
Berthur

Reputation: 4495

If there is a polynomial-time reduction from p1 to p2 it means that if you get an instance of problem p1, then you can transform it (in polynomial time) to an instance of problem p2. What does that tell us about problem p1?

Well, not very much. It means it's decidable, but it doesn't tell us a lot about its time complexity. For all we know, it might be the problem "What is 1+1?".

Had it been the other way around, then it would imply that p1 is NP-hard because otherwise we could solve p2 in polynomial time by reducing it to p1 and solving that in polynomial time.

So, since we don't know anything else about p1, the answer should be b).

Upvotes: 0

Related Questions