Choose the correct statement(s)

A. A problem which is NP-Complete will have the property that it can be solved in polynomial time iff all other NP-complete problems can also be solved in polynomial time.

B. All NP-complete problem are NP-hard problems.

C. If an NP-hard problem can be solved in polynomial time, then all NP-complete problem can be solved in polynomial time

D. All NP-hard-problems are not NP-complete.

Choose the correct answer from the options given below:

The correct answer is Option 4.Key Points

• Statement A: A problem which is NP-Complete will have the property that it can be solved in polynomial time iff all other NP-complete problems can also be solved in polynomial time.
  • This statement is correct. By definition, if one NP-complete problem can be solved in polynomial time, all NP-complete problems can be solved in polynomial time because they are all polynomial-time reducible to each other.
• Statement B: All NP-complete problems are NP-hard problems.
  • This statement is correct. NP-complete problems are a subset of NP-hard problems, meaning every NP-complete problem is also NP-hard.
• Statement C: If an NP-hard problem can be solved in polynomial time, then all NP-complete problems can be solved in polynomial time.
  • This statement is correct. If any NP-hard problem (which is not necessarily in NP) can be solved in polynomial time, it implies that P = NP, meaning all NP-complete problems can also be solved in polynomial time.
• Statement D: All NP-hard problems are not NP-complete.
  • This statement is correct. NP-hard problems include both NP-complete problems and other problems that are not in NP.

Since statements A, B, C, and D are all correct, the correct answer is Option 4.