NP (class)

NP (Nondeterministic Polynomial time) is a class of decision problems in computational theory. Problems in NP are those for which, if the answer is "yes," there exists a certificate or proof that can be verified quickly (in polynomial time). Essentially, NP problems are characterized by the fact that their solutions can be checked efficiently, even if finding the solution initially might be difficult. An important open question is whether every problem in NP can also be solved efficiently (i.e., in polynomial time), which is related to the famous P vs NP problem.