Complexity classes

November 02, 2017

The following notes are meant to act as a reminder for the most popular problem classes.

We indicate a generic problem with ; it can be solved through different algorithms, we indicate with a generic algorithm solving .

Complexity class

We can classify with respect to the following bounds:

  • the cost (in terms of time or memory usage) of executing increase faster than
  • the cost (in terms of time or memory usage) of executing increase as fast as
  • the cost (in terms of time or memory usage) of executing increase slower than

If we have that solving and , then we say belongs to the complexity class of problems solvable with an algorithm with complexity , .

Popular classes of interest include polinomial and exponential .

Non-deterministic polynomial time class (NP)

A problem belongs to the class if:

  • the faster known solving algorithm for X is not polynomial,
  • given a solution for , its correctness can be checked with a polynomial time algorithm.

Reduction

Let’s consider two problems and with solving algorithms respectively. If we can use to solve , it means problem reduces to and, straightforwardly is at most difficult as . One example to this scenario is given with the problem of multiplying two numbers and the problem of computing the value of a squared number; the latter can always be solved using a solving algorithm for the former.

If we can do the same the other way round, using to solve , it means is at most difficult as as well and are said to be equivalent.

Hardness and completeness

Given a problem and a complexity class , if every problem can be reduced to it means that is hard at least as the hardest problem in and so we say is -hard.

If is -hard and then is said to be -complete.

where last equality holds only if all problems are equally difficult.

versus

While it is pretty straightforward that , nor the equality or the proper (strict) inclusion have never been proved. Thus, we only have:

Leaving the hypothesis still not contradicted.