The Gateway to Computer Science Excellence
+5 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 by Boss
retagged by | 1.8k views

2 Answers

+17 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)...
by Active
selected by
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?
class of X has to be subset of NP-C. So, it can be even P rt? How to guarantee it is NP-C?
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
–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
by Boss

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
60,010 answers
94,696 users