1.8k views

For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?

1. If X can be solved in polynomial time, then so can Y
2. X is NP-complete
3. X is NP-hard
4. X is in NP, but not necessarily NP-complete

retagged | 1.8k views

We can't say X is NP hard unless until X is also a NP-complete. X can be NP-complete or below it.. that means it belongs to NP class, in that class(in NP class) it may be NP-complete.. so X is NP for sure but may be NP-complete(but not neccessary).. so option (D)...
by Active
selected by
0
X has to be a subset of NP complete. <= NP complete means it will be atleast NP-complete.
why are we saying that it is NP? the tightest bound will be to say it is NP COMPLETE right?
0
class of X has to be subset of NP-C. So, it can be even P rt? How to guarantee it is NP-C?
0
If X would have been NPC and if X is reducible to Y then Y would have been NP-Hard.
But here Y is NPC and X is reducible to it. In this case can we say anything about X? Please check