edited by
636 views
0 votes
0 votes

A problem $X$ is reducible to problem $Y$ in polynomial time. All the problems in NP can also be reduced to problem $X$. 

Then, which of the following statements are true?

S1 : $X$ is NP complete and $Y$ is in NP.
S2 : $X$ is NP complete and $Y$ is NP hard.
S3 : $X$ and $Y$ are NP complete and hence NP hard.
S4 : $X$ and $Y$ are NP hard.

  1. S4 only
  2. S1, S2 & S3 
  3. S3 & S4
  4. S1, S2, S3 & S4
edited by

1 Answer

Best answer
2 votes
2 votes

"All the problems in NP can also be reduced to problem X," means $X$ is NP-Hard (at least as hard as the hardest problem in NP)

$X$ is reducible to problem $Y$ which makes $Y$ also NP-Hard.

We are not sure if either $X$ or $Y$ is NP-Complete but if $Y$ is NP-Complete $X$ must also be NP-Complete as $X$ can be reducible to Y.

S1 : $X$ is NP complete and $Y$ is in NP ,

False. $X$ need not be NP-Complete as it can lie outside NP-class; same for $Y$.


S2 : $X$ is NP complete and $Y$ is NP hard 

False, $X$ need not be NPC.


S3 : $X$ and $Y$ are NP complete and hence NP-hard

False. As both can lie outside NP-class making them NP-hard but not NP-complete.


S4 : $X$ and $Y$ are NP hard.

True, $X$ and $Y$ are definitely NP-hard as per the statements given.

So, S4 is the only correct statement, which is option A .

selected by
Answer:

Related questions

4 votes
4 votes
0 answers
3
Bikram asked Aug 12, 2017
607 views
The number of possible finite automata with two states $a0$ and $a1$ (where $a0$ is always the initial state over the alphabet $\{p, q\}$) which accepts empty language is...
0 votes
0 votes
1 answer
4
Bikram asked Aug 12, 2017
260 views
What is the regular expression corresponding to the above DFA?$(01 + (00)^*1)^*$$0^*10^*$$(10 + 0(00)^* (1 + 01) )^*$$0(00)^*10^*$