The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
1.1k 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
asked in Algorithms by Boss (19.1k points)
retagged by | 1.1k 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 (5.1k points)
selected by
0
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?
0
class of X has to be subset of NP-C. So, it can be even P rt? How to guarantee it is NP-C?
0
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)
Answer:

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
47,931 questions
52,335 answers
182,383 comments
67,817 users