Another useful property of the class NP is that all NP problems can be solved in exponential time (EXP).
This is because we can always list out all short certificates in exponential time and check all O(2nk) of them.
Thus, P is in NP, and NP is in EXP. Although we know that P is not equal to EXP, it is possible that NP = P, or EXP, or neither. Frustrating!
