5,955 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

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)...

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

@Arjun sir https://www.geeksforgeeks.org/gate-gate-it-2008-question-11/ chech the explanation is it right or wrong?

@Aspi R Osa if X reduces to an NPC problem, then it means X is not harder than NPC. So X is in NP(all problems not in NP are harder than NPC).

Remember this:

Problem X ----------reduced in polynomial time---->NPC  == then X can be P, NP, Np-hard, NPC (can be Anyone)

NPC problem ----------reduced in polynomial time---->Problem X   == then X  is NP-Hard

by

Are you saying that we cant reduce an NPC problem in polynomial time to a problem outside NPC class?

@Arjun sir, edited

X is also as hard as Y So X is np hard..but we dont whether it belongs to np or not so we are not sure whether its np complete or not