P is the set of problems whose solution times are proportional to polynomials involving N's. ... NP (which stands for nondeterministic polynomial time) is the set of problems whose solutions can be verified in polynomial time. But as far as anyone can tell, many of those problems take exponential time to solve.
