> P is a class of problems that are easy to solve and easy to verify. > NP, on the other hand, is a class of problems that are hard to solve yet easy to verify

> P is a class of problems that are easy to solve and easy to verify. > NP, on the other hand, is a class of problems that are hard to solve yet easy to verify. The latter description is not quite correct, as NP includes P. So not all problems in NP are hard to solve. Similarly with EXP. The class of problems that are hard to solve yet easy to verify, is exactly NP\P, which we assume (but cannot prove) is non-empty.