## 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.