An overview of the most important complexity classes of algorithms.

Here is a visual depiction:

# P

Can be *solved* by a *deterministic* Turing machine in polynomial time

# NP

- Can be
*solved*by a*non-deterministic*Turing machine in polynomial time - Can be
*verified*by a*deterministic*Turing machine in polynomial time

# NP-hard

- A problem to which every NP problem can be reduced to in polynomial time
- A problem to which at least one NP-complete problem can be reduced to in polynomial time
**Is not necessarily in NP**

# NP-complete

- Subset of NP-hard
- Those NP-hard problems that are in NP
**Is in NP**