NP stands for nondeterministic polynomial time. One characterization: the set of decision problems solved by a nondeterministic Turing machine in polynomial time.

It is the complexity-class of decision problems solved by a nondeterministic Turing machine in polynomial time. It is equivalently the set of problems whose solution is verifiable in polynomial time by a deterministic Turing machine.

Reference: http://en.wikipedia.org/wiki/NP_%28complexity%29

history | excerpt history