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