NP

Technically speaking:

• A problem is in NP if it has a short accepting certificate.
• An accepting certificate is something that we can use to quickly show that the answer is ``yes'' (if it is yes).
• Quickly means in polynomial time.
• Short means polynomial size.

This means that all problems in P are in NP (since we don't even need a certificate to quickly show the answer is ``yes'').

But other problems in NP may not be in P. Given an integer x, is it composite? How do we know this is in NP?