If an NP-Complete problem can be solved in polynomial time, what would follow?

Options

  • A. P = NP
  • B. P = PSPACE
  • C. NP becomes undecidable
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. P = NP

Detailed Explanation

If any NP-Complete problem is solved by a polynomial-time algorithm, then P = NP. This follows because every problem in NP can be polynomially reduced to an NP-Complete problem. Therefore, a polynomial-time algorithm for one NP-Complete problem could be used, together with the reduction, to solve every problem in NP in polynomial time. This is one of the central consequences of NP-Completeness and explains why finding an efficient algorithm for an NP-Complete problem would be a major theoretical result.