in Algorithms retagged by
5,955 views
10 votes
10 votes

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
in Algorithms retagged by
6.0k views

3 Answers

18 votes
18 votes
Best answer
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)...
selected by

4 Comments

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
0
0

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

0
0

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

0
0
0 votes
0 votes

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

edited by
by

2 Comments

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

@Arjun sir, edited

1
1
–2 votes
–2 votes
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
Answer:

Related questions