retagged by
7,047 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
retagged by

3 Answers

Best answer
18 votes
18 votes
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
1 votes
1 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
–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

6 votes
6 votes
1 answer
3
13 votes
13 votes
5 answers
4