Complexity Classes

At the heart of science and mathematics is classification. When we classify things, they we are essentially recognising they are similar in a certain way.

Likewise, we like to be able to say that a certain class of algorithms are easy and others hard.

Let $C(\Phi)$ be the complexity measure of program $\Phi$. Then the classes are:

1. P
2. NP
3. NP-COMPLETE
4. NP-HARD

In the standard setting, the complexity classes can be written as follows:

$$\subseteq \subseteq \subseteq$$

We will talk in terms of time complexity in explaining the complexity classes.