NP refers to "non-deterministic polynomial time".
NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes."
More precisely, these proofs have to be verifiable in polynomial time by a deterministic Turing machine.
Many natural computer science problems are covered by the class NP. In particular, the decision versions of many interesting search problems and optimization problems are contained in NP.
NP contains many important problems, the hardest of which are called NP-complete problems, for which no polynomial-time algorithms are known. Once a problem has been proven to be NP-complete this is widely regarded as a sign that a polynomial algorithm for this problem is unlikely to exist.
No comments:
Post a Comment