Definition:Nondeterministic Polynomial Time

Definition

Let $D$ be a decision problem.

Let $D$ be such that a particular randomly, that is, nondeterministically selected, candidate solution to $D$ can be determined in polynomial time as to whether it actually is a solution.

Then $D$ runs in nondeterministic polynomial time.

Also known as

Nondeterministic polynomial time can also be hyphenated: non-deterministic polynomial time.

Also see

• Results about nondeterministic polynomial time can be found here.

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): NP problem
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): nondeterministic polynomial time
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): NP problem