Definition:NP

Definition

In computation theory NP is a complexity class where there exists some Nondeterministic Turing Machine that will either halt within $p(|x|)$ steps or run forever where $p$ is a polynomial and $|x|$ is the length of the input to the Machine.

Example

Boolean Satisfiability is NP because a Non-deterministic Turing Machine can pick values for all the variables and determine within $O(|x|)$ steps if the values are a solution to the problem. If they are then the machine stops, otherwise it loops forever.

Notes

If a potential solution to a problem can be verified on a deterministic Turing Machine in polynomial time, then that problem is NP.

Any problem in the complexity class P is also in the class NP because any deterministic Turing Machine is also a non-deterministic Turing Machine.