polynomialsnpreductionnp-completenp-hard

Classifying NP Completeness and Hardness


Choose the correct statement(s):

My answer is (A)(B)(C)(E):


Is answer true?


Solution

  • 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.