| 释义 |
NP problem This is short for ‘nondeterministic polynomial time'. For some problems, there is no known algorithm that solves the problem in polynomial time, but there is a known algorithm which verifies a potential solution as a genuine solution in polynomial time. Such a problem is the travelling salesman problem. It is an open Millennium Prize problem whether NP = P, which means that NP problems can in fact also be solved in polynomial time.
|