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
  4. NP-HARD

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

    P$\displaystyle \subseteq$   NP$\displaystyle \subseteq$   NP-COMPLETE$\displaystyle \subseteq$   NP-HARD

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


Menaka Lashitha Bandara 2005-04-18