Complexity theory is a subject area of ​​theoretical computer science that concerns the design and analysis of algorithms. However, the topic is also relevant in practice. What should one know about it?

The starting point of complexity theory is the task of finding or designing an algorithm for a problem to solve it. Such an algorithm should of course be “good” if possible, that is, meet various criteria. This includes correctness and reliability, but also a high speed and little memory requirement.

However, the speed and the memory requirement often behave in opposite directions, so that one has the choice between a fast algorithm, that uses a lot of memory, and a slow one that is economical with memory. In the simplest case, an algorithm can be accelerated by caching calculated intermediate results, which then increases the memory requirement.

An important question is how to specify the speed of an algorithm at all. Specifying an absolute time is often not useful because it depends on the one hand on the CPU actually used and on the other hand on the size of the input: Of course, it takes longer to get the maximum from a list with 1000 elements to be determined as that from a list with 100 elements.

Therefore, the basic idea of ​​complexity theory is to describe the running time of an algorithm by a function that depends on the input size. In this case, however, it is not about the concrete values ​​determined by the function, but about their type – i.e. whether it is a linear, a quadratic, cubic or other function.

In order to be able to give this description, the so-called O notation exists. An algorithm with a linear effort is therefore called “O (n)”, an algorithm with a quadratic effort is called “O (n ^ 2)” and so on.

What is complexity theory?

Polynomial Complexity The effort to determine the maximum of a list is linear: Since each list element has to be compared at least once with the maximum found so far, it increases The complexity of the algorithm is linear with the number of elements. On the other hand, the effort to form all possible pairs from a list of numbers is quadratic, since each element has to be combined with every other element.

Possible factors are neglected. So it doesn’t matter whether an algorithm has to go through a list once or twice, the effort is linear either way. The reason for this is that, especially for large inputs, a potential factor does not play a role in comparison to the possible powers (in the long term, “x ^ 2” increases faster than “2x” or ” because of the square” x “).

A special case is” O (1) “, which stands for constant effort: In this case, the algorithm always needs the same length, regardless of the size of the input. This is the case, for example, when accessing elements of an array, since the address of the desired element can be calculated directly and is therefore independent of the length of the list.

All functions mentioned so far have in common that they can be described by a polynomial. Algorithms, the runtime of which can be described in polynomial terms, are generally regarded as “good”, since in case of doubt they can be significantly accelerated by a faster CPU, which is why higher problem sizes are possible.

With linear Complexity enables a CPU a hundred times as fast, for example, to solve problems a hundred times as big, with quadratic complexity still ten times as big problems. Algorithms that work with polynomial runtime can therefore be significantly improved with more or better hardware.

Polynomial Complexity

Non-Polynomial Complexity However, this does not apply to those algorithms whose running time is not polynomial, but for example exponential. One problem for which no polynomial running time algorithm has yet been found is the Traveling Sales Person (TSP) problem. This involves a sales representative whose job it is to travel to a number of cities and to choose an optimal route, i.e. the shortest possible route.

The naive solution, Determining every possible route and then choosing the shortest one from these quickly breaks all boundaries. Since there are “n” possibilities for the first city, “n-1” for the second, “n-2” for the third, and so on, the number of possible routes can be calculated by the factorial function, which increases extremely quickly . An algorithm that chooses this approach therefore has a running time that is described by the factorial. It is unknown whether there can be a solution for TSP with polynomial effort.

The problem with such algorithms is that no significant increase in the problem size is possible even with significantly more powerful CPUs, because the problems or their (previous) solutions are simply too complex.

Non-Polynomial Complexity

P, NP & Co. as complexity classes All problems can be categorized into different complexity classes. The simplest class is “P” and contains all those problems for which an algorithm with polynomial running time exists. Contrary to what the name suggests, the class “NP” does not contain those problems that can be solved in non-polynomial time, but rather those problems for which a guessed solution can be checked in polynomial time. “NP” therefore stands for “nondeterministic polynomial”.

However, not all problems in NP are equally difficult. There are particularly difficult and even unsolvable ones, which together make up the class “NP-difficult”. NP and NP-difficult partially overlap. This intersection is again referred to as “NP-complete”. The special thing about NP-complete is that all problems from NP can be mathematically traced back to any NP-complete problem.

That means, if a single problem should succeed Solving NP-completely with polynomial running time would automatically solve all problems from NP in polynomial time. The classes P and NP would be identical in that case. Whether this is the case or not is open.

P, NP & Co. as complexity classes

What is NP-complete? In this sense, the NP-complete problems represent the origin of NP. An example of a NP-complete problem has already been mentioned, namely TSP. Another NP-complete problem is the Knapsack problem, which is about packing a selection of items that optimize the value of the packed items, but taking into account the fact that not any number of items can be packed.

It may be advisable not to choose a large but valuable item, as the combination of two smaller items is more valuable overall and takes up less space in the backpack. This already shows the relationship to TSP: Here, too, it can make sense to skip a very short section of a route and accept a longer one. This applies if the short section leads to an unnecessarily long detour elsewhere.

If one of the NP-complete problems could be solved in polynomial time, P and would be NP equal. However, if P and NP are not the same, then NP and NP-complete are also not the same. NP then contains virtually all “moderate” problems.

Apart from the fact that it has not been proven (or disproved) whether P and NP are equal, it has not even been proven that the Relationship of P and NP is provable at all. That makes the topic particularly exciting and challenging.

What is NP-complete?

Conclusion The topic is of practical relevance because it may be possible to show for a given problem that there can be no “good” solution – that it is pointless to keep looking for a solution, as you will never find one anyway becomes.