Choose the correct statement(s):
X
is an NP-complete problem, then X
is an NP problemX
is an NP-complete problem, then X
is an NP-hardX
be an NP-complete problem. If X
can polynomial reduce to a problem Y
, then Y
is an NP-complete.X
be an NP-complete problem. If Y
can polynomial reduce to a problem X
, then Y
is an NP-complete.X
be an NP-complete problem. If X
can polynomial reduce to a problem Y
, then Y
is an NP-hard.My answer is (A)(B)(C)(E):
Is answer true?
Here are some corrections:
(C) False. Y is NP-hard, but not necessarily in NP.
(D) False. Y is in NP, not necessarily NP-complete.
(E) True, but Y is no necessarily NP-complete.