Notes

The theory of algorithmic complexity to compute efficiently
Why The theory of algorithmic complexity to compute efficiently is important to know that a problem is difficult to solve
The research revolves around two complementary quests. The first is to find the most efficient algorithms possible to solve a problem — this is the so-called quest for upper bounds. The second, which completes it, is to show that an algorithm is indeed the best, this is the so-called quest for lower bounds. In practice, things are more nuanced. The best known lower bound is not always the same as the best known upper bound; one can then be tempted to improve the existing algorithms or to refine the lower bound.

Why look for lower bounds? Understanding that a problem is not effectively solvable can be critically important for several reasons. A difficult problem can be a pledge of security. For example, RSA encryption, widely used to securely exchange data, especially on the Internet, is based on the assumption that factoring a number into its prime factors is a difficult problem for a computer. Demonstrating this intuition would allow us to sleep soundly. Moreover, knowing that a problem is difficult saves us from needlessly searching for effective methods that do not exist. Instead, it seems more reasonable to restrict one's ambitions by seeking, for example, approximate solutions.

Let's count the elementary operations
When executing an algorithm, the computer performs a series of very simple operations such as comparing small numbers for example. We then measure the time complexity of an algorithm as the number of these elementary operations. For example, considering elementary the addition of 2 digits, adding the addition of two numbers of n digits will make us perform n additions to 1 digit, the complexity will therefore be n. On the other hand, asking the multiplication of these same two numbers (by the method learned at school) will have a complexity of the order of n2. The advantage of counting only these operations (and not real time) is to overcome the actual power of the computer. A recent computer will really be much faster than the computer left in the closet since the early 2000s, but the number of elementary operations will remain about the same. In The theory of algorithmic complexity to compute efficiently , we can speak of the intrinsic complexity of a problem: it is the smallest number of elementary operations necessary for an algorithm to solve this problem.

Note that complexity has many aspects. Complexity is most often measured in the worst case, i.e. on the worst instance of the problem. However, sometimes it will be wiser to measure the complexity on average (i.e. the average difficulty of a random instance). Similarly, rather than looking at time, we can also consider space complexity (the memory space needed to solve the problem).

Classifying problems: complexity classes
The theory is interested in understanding how the complexity of a problem will behave according to the size of its input. The goal is to group problems of similar complexity into categories called complexity classes. For example, for a function g(n), we define the class DTIME(g(n)) as the set of problems that can be solved in g(n) elementary operations on an input of size n (for technical reasons, the execution times are in fact to be considered up to a multiplicative constant, but we will ignore this detail!). As seen above, adding two numbers of n digits is resolved in time n therefore belongs to DTIME(n). We can also show that we cannot do better or, in other words, that this problem does not belong to the smaller classes. For multiplication, it is more delicate. As mentioned above, it can be done in n2 operations and one could imagine that this is optimal. This is not the case: the (non-trivial) Schönage-Strassen algorithm shows for example that this problem can be solved in time n log(n) log log(n), which is significantly better than n2! There is a more affordable method, the Karatsuba algorithm, much more efficient than the method learned at school but less efficient than that of Schönage-Strassen.

In The theory of algorithmic complexity to compute efficiently , one of the founding results of the theory was born — the hierarchy theorem of Hartmanis and Stearns. This explains the following adage, intuitive but far from being easy to prove: “having more time allows you to solve strictly more problems”. More formally, this theorem shows that there are problems that can be solved in time h(n) but not in time g(n) when h(n) is significantly larger than g(n).
My Website: https://postheaven.net/patrickweiss9/the-theory-of-algorithmic-complexity-to-compute-efficiently-knbz