The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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
asked in Algorithms by Boss (16.3k points)
retagged by | 1.2k views

2 Answers

+15 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)...
answered by Active (5k points)
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
answered by Boss (14.4k points)

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
49,793 questions
54,514 answers
75,187 users