Unsolvable problems and lower bounds. Lecture by Alexander Shen in 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, efficient algorithms (and even no algorithms at all) do not exist. What is it that they succeed in and fail to do, and why should this be necessary? The lecture deals with the “problem of stopping” and the problems to which it reduces, the famous NP class, as well as simple lower estimates.
The lecture was given in the Small School of Data Analysis, which Yandex organizes for high school students. The author - Alexander Shen. He graduated from the 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 a member of the Institute for Information Transmission Problems. 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 Khanievich wrote about mathematics and programming are freely available .
')
Under the cut - decoding lecture.
There is a standard scheme that everyone always starts with - how computers are generally used: that there is some problem in life, there is its mathematical formulation, there is some kind of algorithm that solves this problem, there is its implementation, well, 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 implemented (automated control systems). It was believed that socialism is accounting and control, and it is necessary that all enterprises have computers, which inform the Council of Ministers how much is 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 become clear that a mathematical problem is unsolvable, that is, there is no algorithm that solves it. Or another option: the task may be solvable, but it is not known how to solve it quickly. And what we encounter every day: everything is solvable, and the algorithms are fast, but the program is wrong, so nothing works. Finally, the program may be correct, but there are problems with its implementation.
We are interested in insoluble problems and complex algorithms. The meaning that interests us is: the problem is algorithmically insoluble, and this is a massive problem. For example, there is Hilbert's 10th problem: a polynomial with integer coefficients (and several variables) needs to be found out if he has a solution. And this cannot be done algorithmically, in principle there is no such algorithm. Another example of a problem that is in principle decidable is that any integer can be factorized by just brute force, but there is no fast 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 with this program whether it will stop or not. The theory of algorithms began from the moment when people proved that this problem was unsolvable. 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. It was all invented before the first processors appeared. The Turing machine, programming languages, was invented. After such a programming language is formulated, you can ask what the program needs to determine if it stops or does not stop. The program that we would like to find, but which is not, when she is given some program A, should say “yes” or “no” depending on whether A stops or does not stop. There are different options for this stop, for example, programs in different programming languages ​​can be viewed, programs with or without an input can be viewed. All these options are equivalent for different programming languages. For example, a company distributes a program that allows it to analyze it in advance for any program for Macintosh and tell whether it stops or does not stop. How can we use this to determine if the Linux program stops? A simpler technical way is to write on the Macintosh an interpreter of the processor on which the Linux system is written, to launch this Linux system accordingly, and all this together will become some program for the Macintosh system, and it will stop only if that program stops. The possibility of broadcasting shows that the programming language is not an essential detail here, and all that matters is whether we are able to determine whether the program will stop for some model or not.
Why is it important to know if the program stops or does not stop? The reason is that so many different tasks come down to this. Suppose we have learned to know whether the 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 if this program will stop or not. This can be done about very many mathematical hypotheses.
There is also a completely extraneous educational program that the set of all binary fractions is uncountable, that all binary fractions cannot be arranged in a sequence. If we write the first fraction, the second, the third, and so on, then there is always a fraction that is omitted. We can build a fraction, which 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 some character for each fraction and make it differ in this sign. If we write these fractions, we can always find a fraction that is not on this list. This is scientifically called the Cantor's Diagonal Argument.
From this we will easily get the option why the stopping problem is unsolvable. Consider not all fractions, but only computable fractions. A binary fraction is called computable if there is an algorithm that writes it out, or there is an algorithm that by position number says what it is worth. All known numbers - “pi”, “e” - are computable, because there are corresponding series. Of course, not all fractions are computable, because computable fractions are only countable, 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 write all the programs that compute these decimals. How then to build an incalculable fraction? You just need to apply the diagonal construction to the programs that calculate all the fractions. It turned out to be a contradiction: it seems that this very fraction, which is not computable, on the other hand, is nonetheless computable. We have a list of these programs, we take the program number I, they are numbered in the usual way, we look at what this program gives in this place, and we write to our fraction not what the program gave us in this place. We get a computable binary fraction, which is not included in the list of all computable binary fractions, we get a contradiction. The problem here is the following: programs are not only that stop everywhere. A program at some inputs may not give any bits at all - neither zero nor one. And we don’t know this in advance, so when I say that we will write down all the programs for infinite binary computable fractions here, this is a scam. And it is that we can write out all the programs, but then some of them in some places will not give anything. And we cannot select from them those programs that give something everywhere, we cannot, and this is the reason for the contradiction.
Why is stopping 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 any inputs or do not stop. Further we would write a new program, indicating that it wants to differ from this program at this place, bearing in mind that there is such a danger. I-th program on the I-th place is not defined, we act carefully. First we ask the problem of stopping: will the I-th program stop at the I-st ​​place. And if she says she will stop, then we boldly launch it, 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. Thus, we got some program that calculates the sequence, and this sequence is not here either in full lines or in lines with gaps. Because if they took any string, then there is a difference in this position. This is an unsolvable problem stopping.
How can undecidability be obtained from this for some specific tasks? This is a game that Conway came up with and is called FRACTRAN . The game is as follows. There is a certain list of fractions of rational numbers - a finite list. And there is some integer - this is the playing field. You are trying to multiply this number by any of these fractions so that an integer number remains. It all fits, if at some point there are already no such numbers, and we finish the work, we see that we cannot multiply anything. It may not converge - this means that we do it all the time and this does not end at all. Conway's theorem - there is no algorithm that, by initial position, determines whether Conway's game will end. This task is algorithmically unsolvable.
Now let's try to prove it. Consider a simple programming language. Simple language has a number of variables. Initially, they are all zero, or rather, there can be any number of variables in the program, but the program is finite, so 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 reduce some variable by one, but here it cannot be reduced, because it is already zero. Then an interrupt occurs in this machine, and in this case we reduce the variable. And, if it is impossible to do, then you need to move to another line of the program. In this language, you can program any program. How, for example, to make an unconditional transition? We need to create some variable that we never increase, and if we want to make an unconditional transition, we can make an attempt 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. Standard mathematical method: you need to take the number 2 to the power x1 multiply by 3 to the power x2 multiply by P n to the power x n . Every prime number is decomposed into prime factors, so we can encode any of our numbers by the powers of these same numbers.
We will now prove this theorem by reducing the programming language to Conway’s game. Our immediate goal is "mixing." The task of stopping the program is reduced to the task of stopping the game, i.e. we have given some program, and we will build a game for this program, which stops only when the program stops. A program is given, and there are some lines in it, some variables and lines. Our task is to build some game that would simulate this program. action in the game of the conveyor must match exactly the execution of this program. For example, there are 26 variables. Then we will encode them by the powers of the first twenty-six prime numbers. Those. the number that in Conway’s game will actually contain the value of all variables. Another game must remember which line of the program is the current one. Which current line is encoded like this: all lines of the program are numbered with even larger prime numbers. The contents of all variables and the current program line are encoded with an integer. The game simulates the behavior of the program at every moment of the game. We have to build the first 26 primes to the degree that are in the value of variables, and then multiply this by a simple number, which is the label of the current line - this makes it easy to imitate our two teams. What do we need to do if in the line with the number of some Q we have some variable C to increase by one? What fractions in the game Conway, we must provide for this? C is coded as a power of five. We need to foresee such a thing in Conway’s game that if we have the current line Q, then we must increase the exponent of the five in our number by one and go to the next line, which has the number R.
Obviously, the numerators will be five, because adding one to C corresponds to multiplying by five. The denominator should have something that would make this fraction work when our current line is Q. So, we need to write Q in the denominator. Then this fraction can only be used if our current number contains Q. Accordingly, it is necessary to multiply on R. In fact, in any sequence of Conway, the sequence of fractions is written: 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, then 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 You can write a sequence of fractions and more. The person playing this game will, in fact, perform this program. From this it will become clear that to determine whether the game stops, if we were able, we could also determine whether the program stops in this language. Before that, we explained that, in principle, a program of any other language can be translated into this language using these techniques. We can transform any program into this game of Konvey, and if someone could say whether the game would stop or not stop, then this could be used to determine whether the program will stop or not. Once we have proved that stopping the program is intractable information, if A comes down to B and B is solvable, then A is solvable. So, if A is reduced to B, and B is unsolvable, then it does not mean anything, because a simple task can be reduced to a complex one. But if we reduced a difficult task to some, then this, then, is also a difficult one. The question of stopping the game Conway is insoluble.
There is such a thing as a problem is solvable, but almost no one knows how to do it quickly, for example, factoring. You can try all the options, but if you have a number of thousands of numbers, then you never try them, and even the fastest computers will not help. There is a certain class of tasks called NP - complete tasks. This is analogous to the problem of stopping, but in the real world, where we are interested in feasibility in some real time. It is not proven whether they can be resolved 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 task 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 reboring problem. If you are trying to program something, and you can see that an NP-complete problem arises, this means that you have to do something, look for a different mathematical model or introduce additional restrictions, or somehow modify the formulation in general.
The lecture was given in the Small School of Data Analysis, which Yandex organizes for high school students. The author - Alexander Shen. He graduated from the 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 a member of the Institute for Information Transmission Problems. 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 Khanievich wrote about mathematics and programming are freely available .
')
Under the cut - decoding lecture.
There is a standard scheme that everyone always starts with - how computers are generally used: that there is some problem in life, there is its mathematical formulation, there is some kind of algorithm that solves this problem, there is its implementation, well, 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 implemented (automated control systems). It was believed that socialism is accounting and control, and it is necessary that all enterprises have computers, which inform the Council of Ministers how much is 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 become clear that a mathematical problem is unsolvable, that is, there is no algorithm that solves it. Or another option: the task may be solvable, but it is not known how to solve it quickly. And what we encounter every day: everything is solvable, and the algorithms are fast, but the program is wrong, so nothing works. Finally, the program may be correct, but there are problems with its implementation.
We are interested in insoluble problems and complex algorithms. The meaning that interests us is: the problem is algorithmically insoluble, and this is a massive problem. For example, there is Hilbert's 10th problem: a polynomial with integer coefficients (and several variables) needs to be found out if he has a solution. And this cannot be done algorithmically, in principle there is no such algorithm. Another example of a problem that is in principle decidable is that any integer can be factorized by just brute force, but there is no fast 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 with this program whether it will stop or not. The theory of algorithms began from the moment when people proved that this problem was unsolvable. 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. It was all invented before the first processors appeared. The Turing machine, programming languages, was invented. After such a programming language is formulated, you can ask what the program needs to determine if it stops or does not stop. The program that we would like to find, but which is not, when she is given some program A, should say “yes” or “no” depending on whether A stops or does not stop. There are different options for this stop, for example, programs in different programming languages ​​can be viewed, programs with or without an input can be viewed. All these options are equivalent for different programming languages. For example, a company distributes a program that allows it to analyze it in advance for any program for Macintosh and tell whether it stops or does not stop. How can we use this to determine if the Linux program stops? A simpler technical way is to write on the Macintosh an interpreter of the processor on which the Linux system is written, to launch this Linux system accordingly, and all this together will become some program for the Macintosh system, and it will stop only if that program stops. The possibility of broadcasting shows that the programming language is not an essential detail here, and all that matters is whether we are able to determine whether the program will stop for some model or not.
Why is it important to know if the program stops or does not stop? The reason is that so many different tasks come down to this. Suppose we have learned to know whether the 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 if this program will stop or not. This can be done about very many mathematical hypotheses.
There is also a completely extraneous educational program that the set of all binary fractions is uncountable, that all binary fractions cannot be arranged in a sequence. If we write the first fraction, the second, the third, and so on, then there is always a fraction that is omitted. We can build a fraction, which 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 some character for each fraction and make it differ in this sign. If we write these fractions, we can always find a fraction that is not on this list. This is scientifically called the Cantor's Diagonal Argument.
From this we will easily get the option why the stopping problem is unsolvable. Consider not all fractions, but only computable fractions. A binary fraction is called computable if there is an algorithm that writes it out, or there is an algorithm that by position number says what it is worth. All known numbers - “pi”, “e” - are computable, because there are corresponding series. Of course, not all fractions are computable, because computable fractions are only countable, 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 write all the programs that compute these decimals. How then to build an incalculable fraction? You just need to apply the diagonal construction to the programs that calculate all the fractions. It turned out to be a contradiction: it seems that this very fraction, which is not computable, on the other hand, is nonetheless computable. We have a list of these programs, we take the program number I, they are numbered in the usual way, we look at what this program gives in this place, and we write to our fraction not what the program gave us in this place. We get a computable binary fraction, which is not included in the list of all computable binary fractions, we get a contradiction. The problem here is the following: programs are not only that stop everywhere. A program at some inputs may not give any bits at all - neither zero nor one. And we don’t know this in advance, so when I say that we will write down all the programs for infinite binary computable fractions here, this is a scam. And it is that we can write out all the programs, but then some of them in some places will not give anything. And we cannot select from them those programs that give something everywhere, we cannot, and this is the reason for the contradiction.
Why is stopping 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 any inputs or do not stop. Further we would write a new program, indicating that it wants to differ from this program at this place, bearing in mind that there is such a danger. I-th program on the I-th place is not defined, we act carefully. First we ask the problem of stopping: will the I-th program stop at the I-st ​​place. And if she says she will stop, then we boldly launch it, 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. Thus, we got some program that calculates the sequence, and this sequence is not here either in full lines or in lines with gaps. Because if they took any string, then there is a difference in this position. This is an unsolvable problem stopping.
How can undecidability be obtained from this for some specific tasks? This is a game that Conway came up with and is called FRACTRAN . The game is as follows. There is a certain list of fractions of rational numbers - a finite list. And there is some integer - this is the playing field. You are trying to multiply this number by any of these fractions so that an integer number remains. It all fits, if at some point there are already no such numbers, and we finish the work, we see that we cannot multiply anything. It may not converge - this means that we do it all the time and this does not end at all. Conway's theorem - there is no algorithm that, by initial position, determines whether Conway's game will end. This task is algorithmically unsolvable.
Now let's try to prove it. Consider a simple programming language. Simple language has a number of variables. Initially, they are all zero, or rather, there can be any number of variables in the program, but the program is finite, so 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 reduce some variable by one, but here it cannot be reduced, because it is already zero. Then an interrupt occurs in this machine, and in this case we reduce the variable. And, if it is impossible to do, then you need to move to another line of the program. In this language, you can program any program. How, for example, to make an unconditional transition? We need to create some variable that we never increase, and if we want to make an unconditional transition, we can make an attempt 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. Standard mathematical method: you need to take the number 2 to the power x1 multiply by 3 to the power x2 multiply by P n to the power x n . Every prime number is decomposed into prime factors, so we can encode any of our numbers by the powers of these same numbers.
We will now prove this theorem by reducing the programming language to Conway’s game. Our immediate goal is "mixing." The task of stopping the program is reduced to the task of stopping the game, i.e. we have given some program, and we will build a game for this program, which stops only when the program stops. A program is given, and there are some lines in it, some variables and lines. Our task is to build some game that would simulate this program. action in the game of the conveyor must match exactly the execution of this program. For example, there are 26 variables. Then we will encode them by the powers of the first twenty-six prime numbers. Those. the number that in Conway’s game will actually contain the value of all variables. Another game must remember which line of the program is the current one. Which current line is encoded like this: all lines of the program are numbered with even larger prime numbers. The contents of all variables and the current program line are encoded with an integer. The game simulates the behavior of the program at every moment of the game. We have to build the first 26 primes to the degree that are in the value of variables, and then multiply this by a simple number, which is the label of the current line - this makes it easy to imitate our two teams. What do we need to do if in the line with the number of some Q we have some variable C to increase by one? What fractions in the game Conway, we must provide for this? C is coded as a power of five. We need to foresee such a thing in Conway’s game that if we have the current line Q, then we must increase the exponent of the five in our number by one and go to the next line, which has the number R.
Obviously, the numerators will be five, because adding one to C corresponds to multiplying by five. The denominator should have something that would make this fraction work when our current line is Q. So, we need to write Q in the denominator. Then this fraction can only be used if our current number contains Q. Accordingly, it is necessary to multiply on R. In fact, in any sequence of Conway, the sequence of fractions is written: 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, then 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 You can write a sequence of fractions and more. The person playing this game will, in fact, perform this program. From this it will become clear that to determine whether the game stops, if we were able, we could also determine whether the program stops in this language. Before that, we explained that, in principle, a program of any other language can be translated into this language using these techniques. We can transform any program into this game of Konvey, and if someone could say whether the game would stop or not stop, then this could be used to determine whether the program will stop or not. Once we have proved that stopping the program is intractable information, if A comes down to B and B is solvable, then A is solvable. So, if A is reduced to B, and B is unsolvable, then it does not mean anything, because a simple task can be reduced to a complex one. But if we reduced a difficult task to some, then this, then, is also a difficult one. The question of stopping the game Conway is insoluble.
There is such a thing as a problem is solvable, but almost no one knows how to do it quickly, for example, factoring. You can try all the options, but if you have a number of thousands of numbers, then you never try them, and even the fastest computers will not help. There is a certain class of tasks called NP - complete tasks. This is analogous to the problem of stopping, but in the real world, where we are interested in feasibility in some real time. It is not proven whether they can be resolved 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 task 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 reboring problem. If you are trying to program something, and you can see that an NP-complete problem arises, this means that you have to do something, look for a different mathematical model or introduce additional restrictions, or somehow modify the formulation in general.
Source: https://habr.com/ru/post/266785/
All Articles