Search code examples
polynomialsnpreductionnp-completenp-hard

Classifying NP Completeness and Hardness

Choose the correct statement(s):

  • (A) If X is an NP-complete problem, then X is an NP problem
  • (B) If X is an NP-complete problem, then X is an NP-hard
  • (C) Let X be an NP-complete problem. If X can polynomial reduce to a problem Y, then Y is an NP-complete.
  • (D) Let X be an NP-complete problem. If Y can polynomial reduce to a problem X, then Y is an NP-complete.
  • (E) Let 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):

  • (A)(B) : X belongs to NP-complete, means X belongs to NP and NP-hard
  • (C) true
  • (D) Y may be P, NP-hard or NP-complete
  • (E) Y is an NP-complete, and it also is an NP-hard

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.