 What are P and NP?

P refers to the set of mathematical problems that can be solved by some deterministic algorithm in polynomial time. NP refers to the set of mathematical problems for which, if someone gave you a potential answer, you could check if it was correct in polynomial time—thus, roughly speaking, NP is the set of problems you could imagine solving in a short time, somehow, at least “non-deterministically.”

For example, say I want to factor a large number. If you were to whisper the correct factors in my ear, I could quickly multiply them together and check that they were correct. So the factoring problem is in NP. We don't know if it is in P—that is, we don't know any deterministic algorithm that will quickly find the factors of a large number.

It is not known if P equals NP or not. A discovery that P equals NP would be the most useful mathematical discovery since calculus, because it would let you rapidly factor large numbers and do many other things. A proof that P does not equal NP (i.e., that some NP problems are too hard to solve in polynomial time) would be less exciting, but would still win you celebrity among computer scientists.