In computational complexity theory, NP is one of the most fundamental complexity classes. The abbreviation NP refers to "Non-deterministic Polynomial time".
Intuitively, NP contains all decision problems for which the 'yes'-answers have simple 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. In an equivalent formal definition, NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine.
The complexity class P is contained in NP, but NP contains many important problems, called NP-complete problems, for which no polynomial-time algorithms are known. The most important open question in complexity theory, the P = NP problem, asks whether such algorithms actually exist for NP-complete problems. It is widely believed that this is not the case.
Reference:
http://en.wikipedia.org/wiki/NP_%28complexity%29
