September 14, 2015 at 13:07Insoluble problems and lower bounds. Alexander Shen's lecture on Yandex
It is clear why theorists find effective algorithms for solving problems of a certain class, and then practitioners implement them. But theorists also try to prove that for some problems there are no efficient algorithms (and even no algorithms at all). What at the same time do they succeed and fail, and why might this be necessary? The lecture deals with the “stopping problem” and the problems to which it comes down, the famous NP class, as well as simple lower bounds.
The lecture was delivered at the Small School of Data Analysis, which Yandex organizes for high school students. The author is Alexander Shen. He graduated from the Mechmath of Moscow State University, under the leadership of Vladimir Uspensky , a student of Kolmogorov, defended his thesis "Algorithmic Variants of the Concept of Entropy." Now he is an employee of the Institute for Information Transmission Problems named after A.A. Kharkevich RAS and Laboratory of the National Center for Scientific Research of France. Research interests: algorithms, Kolmogorov complexity, logic, information theory. Almost all the books that Alexander Hanievich wrote about mathematics and programming are in the public domain .
Under the cut - decoding of the lecture.
There is a standard scheme with which everyone always starts - how computers are generally used: that there is some problem in life, there is its mathematical formulation, there is some algorithm that solves this problem, there is its implementation, and after that it is “implemented ". At each step of this scheme, various obstacles are possible.
The main obstacle: the task itself, which is posed, is generally wrong. In Soviet times, automated control systems were introduced (automated control system - automated control system). It was believed that socialism is accounting and control, and it is necessary that all enterprises have computers that inform the Council of Ministers how much has been produced, where something is missing in the warehouse - in general, complete information. Nothing came of this, not only because the computers were bad, but also because the task was chosen incorrectly. The task may be completely real, but its mathematical formulation is incorrect. It may turn out that the mathematical problem is unsolvable, that is, there is no algorithm that solves it. Or another option: the problem may be solvable, but it is not known how to solve it quickly. And what we face every day: everything is solvable, and the algorithms are fast, but the program is wrong, so nothing works. And finally, the program may be correct, but there are problems with its implementation.
We are interested in unsolvable problems and complex algorithms. The meaning that interests us: the problem is algorithmically insoluble and this is a massive problem. For example, there is Hilbert’s 10th problem: about a polynomial with integer coefficients (and several variables), you need to find out if it has a solution. And this cannot be done algorithmically; in principle, there is no such algorithm. Another example of a problem that is basically solvable is that any integer can be factorized simply by brute force, but there is no quick algorithm.
The first standard problem with which all evidence of unsolvability begins is the problem of stopping. The problem is that you need to find out from this program whether it will stop or not stop. The theory of algorithms began from the moment when people proved that this problem is insoluble. In principle, in order to prove that something is unsolvable, it is necessary to formulate exactly what the algorithm means, because the Euclidean algorithm could be considered without defining the general concept of the algorithm. This was all invented before the first processors appeared. A Turing machine, programming languages, was invented. After such a programming language is formulated, you can ask what the program needs to determine whether it will stop or not stop. The program that we would like to find, but which is not, when she is given some program A, she must say yes or no, depending on whether A stops or does not stop. There are different options for this stop, for example, you can consider programs in different programming languages, you can consider programs with or without input. All of these options are equivalent for different programming languages. For example, a company distributes a program that allows for any Macintosh program to analyze it in advance and say whether it will stop or not. How can we use this to determine if a Linux program will stop? A simpler technical way is to write on the Macintosh the processor interpreter on which the Linux system is written, run this Linux system accordingly, and all this together will become some kind of program for the Macintosh system, and it will stop only when that program stops. The possibility of translation shows that the programming language here is an insignificant detail, but the only important thing is whether we can determine whether the program for a model will stop or not stop.
Why is it important to know if a program is stopping or not stopping? The reason is that a lot of different tasks come down to this. Suppose we learned to find out whether a program stops or not, then we can immediately answer many different questions, for example, we can determine whether Fermat's theorem is true. We need to write a program that is looking for a counterexample, and ask whether this program will stop or not stop. This can be done about so many mathematical hypotheses.
There is also a completely extraneous educational program that the set of all binary fractions is uncountable, that it is impossible to arrange all binary fractions in a sequence. If we write the first fraction, second, third, etc., then there is always a fraction that is skipped. We can construct the fraction that is omitted as follows. It will differ from the first fraction in the first character, from the second fraction in the second character, etc. It is not necessary to take in a row, you can simply take a sign for each fraction and make it differ in this sign. If we write these fractions, we can always find a fraction that is not in this list. This is scientifically called Cantor’s diagonal argument.
From this we easily get the option why the stopping problem is insoluble. We consider not all fractions, but only computable fractions. A binary fraction is called computable if there is an algorithm that writes it out, or if there is an algorithm that says what it is there by the position number. All known numbers — pi, e — are computable, because there are corresponding series. Of course, not all fractions are computable, because there are only countable numbers of computable fractions, and you can do such a thing: we will write all possible programs that compute these fractions. Programs are finite objects; some sequences of bits can be written in ascending order. We will write all the programs that calculate these decimal fractions. How then to construct an uncalculable fraction? You just need to apply the diagonal construction to programs that calculate all fractions. The contradiction turned out: it seems that this very fraction, which is not computable, on the other hand, is still computable. We have a list of these programs, we take program number I, they are numbered in the usual manner, look at what this program gives in this place, and write in our fraction not what the program gave us in this place. We get a computable binary fraction that is not included in the list of all computable binary fractions, we get a contradiction. The problem here is this: there are more than just programs that stop everywhere. Some program on some inputs may not produce any bits at all - neither zero nor one. And we don’t know this beforehand, so when I say that we write here all the programs for infinite binary computable fractions, this is a scam. And it consists in the fact that we can write out all the programs, but then some of them will not give anything in some places. And we cannot isolate from them those programs that give something everywhere, and this is the reason for the contradiction.
Why is the stop problem unsolvable? Imagine that it would be solvable, then we could correct our reasoning. We would make a list of all programs, regardless of whether they stop at some inputs or do not stop. Further, we would write a new program, indicating that it wants to differ from this program in this place, bearing in mind that there is such a danger. The I-th program at the I-th place is not defined, we are acting carefully. First we ask the stop problem: will the I-th program stop at the I-th place. And, if she says that she will stop, then we boldly start her, wait for this answer and write the wrong bit. And if he says that he will not stop, then we write, for example, zero, because we know that this program will not stop and therefore it is easy to distinguish from it. You can write any number, and it will still not be the same as our program gives. Thus, we got some program that calculates the sequence, and this sequence is not here either in full lines or in lines with spaces. Because if you took any line, then in the total position there is a difference. This is an unsolvable stopping problem.
How can one get unsolvability from this for any specific problems? This is the game that Conway invented , and it's called FRACTRAN . The game is as follows. There is some list of fractions of rational numbers - a finite list. And there is some integer - this is such a playing field. You are trying to multiply this number by any of these fractions so that an integer remains. Everything converges, if at some point there are already no such numbers, and we finish the work, we see that it’s impossible to multiply by anything. It may not converge - this means that we do this all the time and this does not end with anything. Conway's theorem - there is no algorithm that, based on the initial position, determines whether the game of Conway will end. This problem is algorithmically unsolvable.
Now let's try to prove it. Consider a simple programming language. A simple language has a number of variables. Initially, they are all equal to zero, or rather, in the program of variables there can be as many as you like, but the program is finite, therefore it includes only a finite number. Variables are all natural numbers. We have two teams: the first command is to increase the counter by one, the second command is to decrease some variable by one, but here it cannot be decreased, because it is already equal to zero. Then an interrupt occurs in this machine, and in this case we reduce the variable. And, if this cannot be done, then you need to go to another line of the program. You can program any program in this language. How, for example, to make an unconditional transition? We need to get some variable that we never increase, and if we want to make an unconditional transition, we can try to reduce this variable, and then we will make this transition. If we have a finite number of variables in the program, then how to implement arrays? We must encode the array in one number. The standard mathematical method: you need to take the number 2 in degreex1 multiply by 3 to the power of x2 multiply by P n to the power of x n . Every prime number is decomposed into prime factors, so we can encode our any numbers with powers of these same numbers.
We will now prove this theorem by reducing the programming language to the game Conway. Our immediate goal is “mixing.” The task of stopping the program is reduced to the problem of stopping the game, i.e. we have given some program, and under this program we will build a game that stops only when the program stops. Some program is given, and there are some lines in it, there are as many variables and lines as possible. Our task is to build some game that would simulate this program i.e. the action in the convoy game must correspond exactly to the execution of this program. For example, the variables are 26. Then we will code them with powers of the first twenty-six prime numbers. Those. the number that in the game Conway will actually contain the value of all variables. Another game must remember which line of the program is current. Which current line is encoded like this: we will number all lines of the program with even larger primes. The contents of all variables and the current line of the program is encoded as an integer. The game simulates the behavior of the program at every moment of the game. We need to raise the first 26 primes to powers that are in the value of the variables, and then multiply this by the prime number, which is the label of the current line, this will easily simulate our two teams. What do we need to do if, in the line with the number some Q, we need some variable C to be increased by one? What fractions in Conway’s game should we provide for this? C is encoded as a power of five. In Conway’s game, we have to provide for such a thing that if we have the current line is Q,
Obviously, there will be five in the numerators, because adding one to C corresponds to multiplying by five. There should be something in the denominator that would let this fraction work when our current line is Q. Therefore, we need to write Q in the denominator. Then, using this fraction will be possible only when our current number contains Q. Accordingly, we need to multiply this on R. In fact, in any Conway sequence of fractions we write: here is a fraction. And it works when necessary, in the remaining fractions there will be other denominators, so if the current line is Q, only this fraction can work, and it turns out what is needed, and the new line will be R. If we have such a program, then we can write a sequence of fractions and more. The person playing this game will actually execute this program. From here it will become clear that to determine whether the game stops, if we knew how to do it, we could also determine whether the program stops in this language. Before that, we explained that, in principle, it is possible to translate a program of any other language into this language using these techniques. We can convert any program into this Conway game, and if someone could tell whether this game will stop or not, then this could be used to determine if this program will stop or not. Since we have proved that a program stop is unsolvable information, if A reduces to B and B is decidable, then A is decidable. So, if A reduces to B, and B is unsolvable, then this does not mean anything, because a simple task can be reduced to a complex one. But if we reduced a difficult task to a certain one, then this, therefore, is also difficult.
There is such a thing as the problem is solvable, but almost no one knows how to do it quickly, for example, factorization. You can try all the options, but if you have a number of thousands of numbers, then you will never try them, and even the fastest computers will not help. There is a certain class of problems called NP - complete tasks. This is an analogue of the problem of stopping, but in the real world, where we are interested in feasibility for some real time. It is not proven whether they can be solved quickly. They are all equally complex, if one could be solved quickly, then everything could be solved quickly. This is proved by accepting the reduction of one problem to another. We are looking for an object with some property, while the property itself is a small object, and the property is simple, and the only problem is that there are many objects - this is called a brute force task. If you are trying to program something, and it is clear that an NP-complete problem arises, this means that you need to do something, you need to look for another mathematical model or introduce additional restrictions, or somehow modify the formulation in general.
The lecture was delivered at the Small School of Data Analysis, which Yandex organizes for high school students. The author is Alexander Shen. He graduated from the Mechmath of Moscow State University, under the leadership of Vladimir Uspensky , a student of Kolmogorov, defended his thesis "Algorithmic Variants of the Concept of Entropy." Now he is an employee of the Institute for Information Transmission Problems named after A.A. Kharkevich RAS and Laboratory of the National Center for Scientific Research of France. Research interests: algorithms, Kolmogorov complexity, logic, information theory. Almost all the books that Alexander Hanievich wrote about mathematics and programming are in the public domain .
Under the cut - decoding of the lecture.
There is a standard scheme with which everyone always starts - how computers are generally used: that there is some problem in life, there is its mathematical formulation, there is some algorithm that solves this problem, there is its implementation, and after that it is “implemented ". At each step of this scheme, various obstacles are possible.
The main obstacle: the task itself, which is posed, is generally wrong. In Soviet times, automated control systems were introduced (automated control system - automated control system). It was believed that socialism is accounting and control, and it is necessary that all enterprises have computers that inform the Council of Ministers how much has been produced, where something is missing in the warehouse - in general, complete information. Nothing came of this, not only because the computers were bad, but also because the task was chosen incorrectly. The task may be completely real, but its mathematical formulation is incorrect. It may turn out that the mathematical problem is unsolvable, that is, there is no algorithm that solves it. Or another option: the problem may be solvable, but it is not known how to solve it quickly. And what we face every day: everything is solvable, and the algorithms are fast, but the program is wrong, so nothing works. And finally, the program may be correct, but there are problems with its implementation.
We are interested in unsolvable problems and complex algorithms. The meaning that interests us: the problem is algorithmically insoluble and this is a massive problem. For example, there is Hilbert’s 10th problem: about a polynomial with integer coefficients (and several variables), you need to find out if it has a solution. And this cannot be done algorithmically; in principle, there is no such algorithm. Another example of a problem that is basically solvable is that any integer can be factorized simply by brute force, but there is no quick algorithm.
The first standard problem with which all evidence of unsolvability begins is the problem of stopping. The problem is that you need to find out from this program whether it will stop or not stop. The theory of algorithms began from the moment when people proved that this problem is insoluble. In principle, in order to prove that something is unsolvable, it is necessary to formulate exactly what the algorithm means, because the Euclidean algorithm could be considered without defining the general concept of the algorithm. This was all invented before the first processors appeared. A Turing machine, programming languages, was invented. After such a programming language is formulated, you can ask what the program needs to determine whether it will stop or not stop. The program that we would like to find, but which is not, when she is given some program A, she must say yes or no, depending on whether A stops or does not stop. There are different options for this stop, for example, you can consider programs in different programming languages, you can consider programs with or without input. All of these options are equivalent for different programming languages. For example, a company distributes a program that allows for any Macintosh program to analyze it in advance and say whether it will stop or not. How can we use this to determine if a Linux program will stop? A simpler technical way is to write on the Macintosh the processor interpreter on which the Linux system is written, run this Linux system accordingly, and all this together will become some kind of program for the Macintosh system, and it will stop only when that program stops. The possibility of translation shows that the programming language here is an insignificant detail, but the only important thing is whether we can determine whether the program for a model will stop or not stop.
Why is it important to know if a program is stopping or not stopping? The reason is that a lot of different tasks come down to this. Suppose we learned to find out whether a program stops or not, then we can immediately answer many different questions, for example, we can determine whether Fermat's theorem is true. We need to write a program that is looking for a counterexample, and ask whether this program will stop or not stop. This can be done about so many mathematical hypotheses.
There is also a completely extraneous educational program that the set of all binary fractions is uncountable, that it is impossible to arrange all binary fractions in a sequence. If we write the first fraction, second, third, etc., then there is always a fraction that is skipped. We can construct the fraction that is omitted as follows. It will differ from the first fraction in the first character, from the second fraction in the second character, etc. It is not necessary to take in a row, you can simply take a sign for each fraction and make it differ in this sign. If we write these fractions, we can always find a fraction that is not in this list. This is scientifically called Cantor’s diagonal argument.
From this we easily get the option why the stopping problem is insoluble. We consider not all fractions, but only computable fractions. A binary fraction is called computable if there is an algorithm that writes it out, or if there is an algorithm that says what it is there by the position number. All known numbers — pi, e — are computable, because there are corresponding series. Of course, not all fractions are computable, because there are only countable numbers of computable fractions, and you can do such a thing: we will write all possible programs that compute these fractions. Programs are finite objects; some sequences of bits can be written in ascending order. We will write all the programs that calculate these decimal fractions. How then to construct an uncalculable fraction? You just need to apply the diagonal construction to programs that calculate all fractions. The contradiction turned out: it seems that this very fraction, which is not computable, on the other hand, is still computable. We have a list of these programs, we take program number I, they are numbered in the usual manner, look at what this program gives in this place, and write in our fraction not what the program gave us in this place. We get a computable binary fraction that is not included in the list of all computable binary fractions, we get a contradiction. The problem here is this: there are more than just programs that stop everywhere. Some program on some inputs may not produce any bits at all - neither zero nor one. And we don’t know this beforehand, so when I say that we write here all the programs for infinite binary computable fractions, this is a scam. And it consists in the fact that we can write out all the programs, but then some of them will not give anything in some places. And we cannot isolate from them those programs that give something everywhere, and this is the reason for the contradiction.
Why is the stop problem unsolvable? Imagine that it would be solvable, then we could correct our reasoning. We would make a list of all programs, regardless of whether they stop at some inputs or do not stop. Further, we would write a new program, indicating that it wants to differ from this program in this place, bearing in mind that there is such a danger. The I-th program at the I-th place is not defined, we are acting carefully. First we ask the stop problem: will the I-th program stop at the I-th place. And, if she says that she will stop, then we boldly start her, wait for this answer and write the wrong bit. And if he says that he will not stop, then we write, for example, zero, because we know that this program will not stop and therefore it is easy to distinguish from it. You can write any number, and it will still not be the same as our program gives. Thus, we got some program that calculates the sequence, and this sequence is not here either in full lines or in lines with spaces. Because if you took any line, then in the total position there is a difference. This is an unsolvable stopping problem.
How can one get unsolvability from this for any specific problems? This is the game that Conway invented , and it's called FRACTRAN . The game is as follows. There is some list of fractions of rational numbers - a finite list. And there is some integer - this is such a playing field. You are trying to multiply this number by any of these fractions so that an integer remains. Everything converges, if at some point there are already no such numbers, and we finish the work, we see that it’s impossible to multiply by anything. It may not converge - this means that we do this all the time and this does not end with anything. Conway's theorem - there is no algorithm that, based on the initial position, determines whether the game of Conway will end. This problem is algorithmically unsolvable.
Now let's try to prove it. Consider a simple programming language. A simple language has a number of variables. Initially, they are all equal to zero, or rather, in the program of variables there can be as many as you like, but the program is finite, therefore it includes only a finite number. Variables are all natural numbers. We have two teams: the first command is to increase the counter by one, the second command is to decrease some variable by one, but here it cannot be decreased, because it is already equal to zero. Then an interrupt occurs in this machine, and in this case we reduce the variable. And, if this cannot be done, then you need to go to another line of the program. You can program any program in this language. How, for example, to make an unconditional transition? We need to get some variable that we never increase, and if we want to make an unconditional transition, we can try to reduce this variable, and then we will make this transition. If we have a finite number of variables in the program, then how to implement arrays? We must encode the array in one number. The standard mathematical method: you need to take the number 2 in degreex1 multiply by 3 to the power of x2 multiply by P n to the power of x n . Every prime number is decomposed into prime factors, so we can encode our any numbers with powers of these same numbers.
We will now prove this theorem by reducing the programming language to the game Conway. Our immediate goal is “mixing.” The task of stopping the program is reduced to the problem of stopping the game, i.e. we have given some program, and under this program we will build a game that stops only when the program stops. Some program is given, and there are some lines in it, there are as many variables and lines as possible. Our task is to build some game that would simulate this program i.e. the action in the convoy game must correspond exactly to the execution of this program. For example, the variables are 26. Then we will code them with powers of the first twenty-six prime numbers. Those. the number that in the game Conway will actually contain the value of all variables. Another game must remember which line of the program is current. Which current line is encoded like this: we will number all lines of the program with even larger primes. The contents of all variables and the current line of the program is encoded as an integer. The game simulates the behavior of the program at every moment of the game. We need to raise the first 26 primes to powers that are in the value of the variables, and then multiply this by the prime number, which is the label of the current line, this will easily simulate our two teams. What do we need to do if, in the line with the number some Q, we need some variable C to be increased by one? What fractions in Conway’s game should we provide for this? C is encoded as a power of five. In Conway’s game, we have to provide for such a thing that if we have the current line is Q,
Obviously, there will be five in the numerators, because adding one to C corresponds to multiplying by five. There should be something in the denominator that would let this fraction work when our current line is Q. Therefore, we need to write Q in the denominator. Then, using this fraction will be possible only when our current number contains Q. Accordingly, we need to multiply this on R. In fact, in any Conway sequence of fractions we write: here is a fraction. And it works when necessary, in the remaining fractions there will be other denominators, so if the current line is Q, only this fraction can work, and it turns out what is needed, and the new line will be R. If we have such a program, then we can write a sequence of fractions and more. The person playing this game will actually execute this program. From here it will become clear that to determine whether the game stops, if we knew how to do it, we could also determine whether the program stops in this language. Before that, we explained that, in principle, it is possible to translate a program of any other language into this language using these techniques. We can convert any program into this Conway game, and if someone could tell whether this game will stop or not, then this could be used to determine if this program will stop or not. Since we have proved that a program stop is unsolvable information, if A reduces to B and B is decidable, then A is decidable. So, if A reduces to B, and B is unsolvable, then this does not mean anything, because a simple task can be reduced to a complex one. But if we reduced a difficult task to a certain one, then this, therefore, is also difficult.
There is such a thing as the problem is solvable, but almost no one knows how to do it quickly, for example, factorization. You can try all the options, but if you have a number of thousands of numbers, then you will never try them, and even the fastest computers will not help. There is a certain class of problems called NP - complete tasks. This is an analogue of the problem of stopping, but in the real world, where we are interested in feasibility for some real time. It is not proven whether they can be solved quickly. They are all equally complex, if one could be solved quickly, then everything could be solved quickly. This is proved by accepting the reduction of one problem to another. We are looking for an object with some property, while the property itself is a small object, and the property is simple, and the only problem is that there are many objects - this is called a brute force task. If you are trying to program something, and it is clear that an NP-complete problem arises, this means that you need to do something, you need to look for another mathematical model or introduce additional restrictions, or somehow modify the formulation in general.