NP-hardness
An example of a problem that is at least as hard to solve as any other problem that we can quickly check solutions for, but that can not be checked quickly (it is NP-hard, but it is not NP):