NP

The class NP consists of those problems that are “verifiable” in polynomial time.

What do we mean by verifiable?

• If we were given a “certificate” of a solution, then we could verify that the certificate is correct in time polynomial in the size of the input to the problem.

What does it mean to be as hard as any problem in NP?