Why I do not believe in simple algorithms for NP-complete problems
Recently, this blog published an open letter to scientists about the proposed polynomial algorithm for the 3-SAT problem. The discussion on this topic is far from being closed and it’s premature to find errors in the algorithm, but I want to write why the “citizens of scientists” are not lining up to quickly verify this evidence.
About six months ago, in August of 2010, an attempt was made to prove that P ≠NP. Then one mathematician-blogger, Scott Oronson, in order not to appear unsubstantiated in his distrust of this evidence, put his house on the fact that the proof would be erroneous. Perhaps, I will not lose anything if I follow (with a smaller scale) his example and put on the fact that the current algorithm is wrong with your car (Auris, 2008).
In my opinion, Oronsson risked a little. Vinod Deolalikar, the author of the proof is a relatively well-known mathematician, the P P NP task falls within his area of ​​competence, and the proof itself used several fundamentally new ideas that give hope that with the help of them it will be possible to circumvent the difficulties that those who tried to prove this fact is up to him. With current evidence, the situation is slightly different.
First, what speaks in his favor. The proof is written reasonably well, its author has a mathematical background, and most importantly, in addition to the article about the algorithm, there is its working implementation.
')
Now about why I do not believe that this algorithm may be correct.
To begin with, today there is a consensus among scientists involved in the theory of complexity and generally theoretical computer science that P is not equal to NP, that is, fast algorithms for tasks such as traveling salesman problems, 3-SAT, SAT, backpack problems etc. does not exist. Why do scientists think so? Because in the last few decades, hundreds of NP-complete problems have become known, up to the problem of the optimal algorithm for playing sapper. It is enough to solve at least one of these problems so that all of them are solved. And yet, despite the best efforts of thousands of people, no progress has been made towards creating algorithms for these tasks.
Even if we imagine that someday it turns out that P = NP, then the proof of this fact and the algorithm for solving NP-complete problems must use some fundamentally new ideas, some methods that we do not own now. Deolalikar, for example, used statistical methods in his attempt at proof. As a rule, breakthroughs in old complex tasks occur this way. Fermat's theorem was proved only by constructing a large theory around it from the field of algebraic geometry.
Paradoxically, the current evidence does not add to the fact that it is rather short: its essential parts take up hardly 2-3 pages. For comparison, the proof of the Fermat theorem takes 200-300 pages, not including preliminary information from the used sections of mathematics.
The last and probably the main reason for mistrust is contained in the method of proof itself. In order not to go into details, I will draw an analogy. Imagine that you are solving sudoku (yes, solving sudoku is also an NP-complete task). Suppose you do this in the following way: you fix a few rules for yourself, and then go around the table, applying them in a certain order. Rules must be local type:
- The line already contains this number, so this number cannot stand in other cells of the line.
- Only two numbers X and Y can stand in two square cells, so these numbers cannot stand in other square cells.
etc.
So, if sudoku is simple, then it is quite possible that using only these rules, you can solve it. But in a complex sudoku you will not have to apply, apart from the blunt application of the rules, to sort out any options.
The situation with the algorithm under discussion is approximately the same as with the method of playing sudoku. It contains several rules, according to which we reject decisions that are not suitable for us. The problem is that, just like in Sudoku, this should not be enough in the 3-SAT task.
PS Please do not take this post as a refutation of the algorithm. These are just heuristic reasons why this algorithm should not work. The author of the previous post promised to publish a sequel tomorrow, in which he will answer questions in the comments.
About six months ago, in August of 2010, an attempt was made to prove that P ≠NP. Then one mathematician-blogger, Scott Oronson, in order not to appear unsubstantiated in his distrust of this evidence, put his house on the fact that the proof would be erroneous. Perhaps, I will not lose anything if I follow (with a smaller scale) his example and put on the fact that the current algorithm is wrong with your car (Auris, 2008).
In my opinion, Oronsson risked a little. Vinod Deolalikar, the author of the proof is a relatively well-known mathematician, the P P NP task falls within his area of ​​competence, and the proof itself used several fundamentally new ideas that give hope that with the help of them it will be possible to circumvent the difficulties that those who tried to prove this fact is up to him. With current evidence, the situation is slightly different.
First, what speaks in his favor. The proof is written reasonably well, its author has a mathematical background, and most importantly, in addition to the article about the algorithm, there is its working implementation.
')
Now about why I do not believe that this algorithm may be correct.
To begin with, today there is a consensus among scientists involved in the theory of complexity and generally theoretical computer science that P is not equal to NP, that is, fast algorithms for tasks such as traveling salesman problems, 3-SAT, SAT, backpack problems etc. does not exist. Why do scientists think so? Because in the last few decades, hundreds of NP-complete problems have become known, up to the problem of the optimal algorithm for playing sapper. It is enough to solve at least one of these problems so that all of them are solved. And yet, despite the best efforts of thousands of people, no progress has been made towards creating algorithms for these tasks.
Even if we imagine that someday it turns out that P = NP, then the proof of this fact and the algorithm for solving NP-complete problems must use some fundamentally new ideas, some methods that we do not own now. Deolalikar, for example, used statistical methods in his attempt at proof. As a rule, breakthroughs in old complex tasks occur this way. Fermat's theorem was proved only by constructing a large theory around it from the field of algebraic geometry.
Paradoxically, the current evidence does not add to the fact that it is rather short: its essential parts take up hardly 2-3 pages. For comparison, the proof of the Fermat theorem takes 200-300 pages, not including preliminary information from the used sections of mathematics.
The last and probably the main reason for mistrust is contained in the method of proof itself. In order not to go into details, I will draw an analogy. Imagine that you are solving sudoku (yes, solving sudoku is also an NP-complete task). Suppose you do this in the following way: you fix a few rules for yourself, and then go around the table, applying them in a certain order. Rules must be local type:
- The line already contains this number, so this number cannot stand in other cells of the line.
- Only two numbers X and Y can stand in two square cells, so these numbers cannot stand in other square cells.
etc.
So, if sudoku is simple, then it is quite possible that using only these rules, you can solve it. But in a complex sudoku you will not have to apply, apart from the blunt application of the rules, to sort out any options.
The situation with the algorithm under discussion is approximately the same as with the method of playing sudoku. It contains several rules, according to which we reject decisions that are not suitable for us. The problem is that, just like in Sudoku, this should not be enough in the 3-SAT task.
PS Please do not take this post as a refutation of the algorithm. These are just heuristic reasons why this algorithm should not work. The author of the previous post promised to publish a sequel tomorrow, in which he will answer questions in the comments.
Source: https://habr.com/ru/post/112305/
All Articles