What is the defining characteristic of an NP problem?
Options
-
A.
It can always be solved in constant time
-
B.
A proposed solution can be verified in polynomial time
-
C.
It cannot be solved by a computer
-
D.
More than one of the above
-
E.
None of the above
Correct Answer (Detailed Explanation is Below)
B.
A proposed solution can be verified in polynomial time
Detailed Explanation
- NP: Nondeterministic Polynomial Time.
- A given solution or certificate for an NP decision problem can be verified in polynomial time.
- Important: NP does not mean Non-Polynomial.
- Whether P = NP is still an unsolved problem.
