A polynomial algorithm for a combinatorial problem (P = NP?)
In this article I would like to talk about my research on the topic of equality of classes P and NP. You can read the original article here .
A little introduction.
In general, the problem of equality of classes is one of the most important open mathematical problems. After all, with a positive response, programmers will be able to much optimize many aspects of the program, as well as scientists can, for example, decipher the genome in a short time. However, many scientists are inclined to a negative answer. I, as a programmer, cannot conceive a negative answer, and even if we look, we have already invented algorithms that reduce the iteration time many times over than by going through all the iterations.
')
In my article, everything is written quite sophisticated and difficult to understand, here I would like to tell you in a simple way about this study, as well as supplement the article with new interesting discoveries, and also share with you this polynomial algorithm for quickly calculating combinatorial problems of this kind .
Formulation of the problem:
This is a complete undirected graph. Full - because all the vertices interact with others, undirected - because the graph has no directions.
And it is more convenient to consider graphs in the form of different matrices, for example, we will consider a matrix of edges connecting vertices:
We can imagine these 5 vertices as 5 employees. Imagine that we have an assignment for them and we know how employees interact with each other. For example, 1 and 2 employees will cope with this task worse (their combination is -3) than 1 and 4 (their combination is 2). And let's say 1.3 and 4 employees (their combination 1 + 2 + 3 = 6) perform the task better. The main thing to understand how to find a combination. If it's still hard to understand, then youtu.be/7rKXqprYR2E?t=1h8m52s video. Task setting is the same.
The task is to find the maximum number in combinations.
Now the solution.
In general, the formula helped me find this solution:
The elements are the number found in the largest combination, in this case 12345. Either the sum of all the elements of the matrix, only divided by 2. Since we are symmetric with respect to the diagonal, we can divide.
Now let's talk about decomposition of the matrix, finding profitable vectors, and so de optimal vector and already solutions, of course, the article is quite difficult, everything is described, but we can do it quite quickly, let's start:
First we need to find the maximum element in the matrix - this is 5 and the corresponding combination is 4.5.
The next step is to check for the presence of negative elements in the matrix B, this can be done as follows:
We add vertically (horizontally, not fundamentally) all the elements and see if there are negative numbers here, if not, the combination will be maximum, that is, 1,2,3,4,5. However, -2 is present here, we go further.
The next step is to find profitable vectors. It’s not convenient to do matrix transpositions, especially for a programmer, you can do the following (however, I will show an even more profitable way later):
We cross out the line corresponding to the profitable vector, and the remaining elements are summarized:
Profitable vector O1
Profitable vector O2
Profitable vector O3
And so on to O5, and immediately afterwards we calculate the sum of the elements in each vector:
We find the largest number of the sums - 18, so the O2 vector will be optimal and it contains the solution.
Consider the algorithm for how to get this solution. We find negative elements in this vector and summarize them, in our case, just -2. If we multiply by minus one, change the sign, we get the difference. The difference between the number for the largest combination and the answer we need to find, if simple, is x + r = y. x is either the sum of all elements divided by 2, or just the number from the largest combination. We substitute in the formula, we get 8 + 2 = 10. This will be the numerical solution of the matrix. However, we need to know exactly the vertices (workers) that make up the combination. Just take the column numbers for all positive numbers of the O2 vector: 1,3,4,5. This combination is the desired one.
Why we were looking for the maximum element (5) - if suddenly the solution is less than this element, then the combination will correspond to this element, and not the combination in the vector O.
There is a way to quickly determine the desired combination, without O vectors, but it is important for me that you pay attention to the resulting matrix of O vectors, if all its elements are added, we get the sum of all combinations (in this case 64, you can check it using the formula above). Thus, the matrix is the matrix of all combinations of the graph (workers). The way, for example, for a graph of size 20x20, the number of combinations is 1048575 and they all fit into this matrix of 20 orders, and the optimal solution is found, it is simply amazing!
And now let's solve this problem a bit faster:
1. We write out the sum of all elements and the maximum number.
2. Here B is useful to us, each element is subtracted from the sum of all elements, and the most favorable answer is determined by the advantageous vector.
Following the example of O2: 16 - (- 2) = 18. We have significantly reduced the execution time of the algorithm.
3. Further in the same way as previously we obtain the vector O2 and find the solution.
The number of steps does not exceed the second degree polynomial, you can see for yourself.
Some screenshots from the verification program:
4x4 matrix, decomposition and enumeration method
Matrix 50x50, 0.039 sec. on the decision
Matrix 100x100, 0.069 sec. on the decision
How are things going with other tasks? With the task of a traveling salesman things are good, but not very. For example, if we obtain the matrix of vectors O and the matrix of vectors O for the transposed matrix, then again we will get the matrix of all combinations, but here we have the combinations of Hamiltonian cycles:
In fact, I have not fully understood the task of the traveling salesman, but for the graph n = 4 it works, and for graphs n> 4 it does not work, because I need to rearrange the matrix of combinations a bit before I understand how.
This algorithm can actually help in many planning tasks, such as, for example, the same task of selecting employees for the task of efficiency, ideal training programs, nutrition, in principle, the application is unlimited.
The matrix of combinations is a thing that is not completely known to me and I would be glad if you could help to understand what it is and how to work with it.
Upd: finding the most clicks on this algorithm:
-2 - to designate that the vertices are not connected, 1 - that are connected, in the graph from the picture just 5 clicks and the maximum click - 1,2,3,4. The principle of finding a clique is the same.
A little introduction.
In general, the problem of equality of classes is one of the most important open mathematical problems. After all, with a positive response, programmers will be able to much optimize many aspects of the program, as well as scientists can, for example, decipher the genome in a short time. However, many scientists are inclined to a negative answer. I, as a programmer, cannot conceive a negative answer, and even if we look, we have already invented algorithms that reduce the iteration time many times over than by going through all the iterations.
')
In my article, everything is written quite sophisticated and difficult to understand, here I would like to tell you in a simple way about this study, as well as supplement the article with new interesting discoveries, and also share with you this polynomial algorithm for quickly calculating combinatorial problems of this kind .
Formulation of the problem:
This is a complete undirected graph. Full - because all the vertices interact with others, undirected - because the graph has no directions.
And it is more convenient to consider graphs in the form of different matrices, for example, we will consider a matrix of edges connecting vertices:
We can imagine these 5 vertices as 5 employees. Imagine that we have an assignment for them and we know how employees interact with each other. For example, 1 and 2 employees will cope with this task worse (their combination is -3) than 1 and 4 (their combination is 2). And let's say 1.3 and 4 employees (their combination 1 + 2 + 3 = 6) perform the task better. The main thing to understand how to find a combination. If it's still hard to understand, then youtu.be/7rKXqprYR2E?t=1h8m52s video. Task setting is the same.
The task is to find the maximum number in combinations.
Now the solution.
In general, the formula helped me find this solution:
The elements are the number found in the largest combination, in this case 12345. Either the sum of all the elements of the matrix, only divided by 2. Since we are symmetric with respect to the diagonal, we can divide.
Now let's talk about decomposition of the matrix, finding profitable vectors, and so de optimal vector and already solutions, of course, the article is quite difficult, everything is described, but we can do it quite quickly, let's start:
First we need to find the maximum element in the matrix - this is 5 and the corresponding combination is 4.5.
The next step is to check for the presence of negative elements in the matrix B, this can be done as follows:
We add vertically (horizontally, not fundamentally) all the elements and see if there are negative numbers here, if not, the combination will be maximum, that is, 1,2,3,4,5. However, -2 is present here, we go further.
The next step is to find profitable vectors. It’s not convenient to do matrix transpositions, especially for a programmer, you can do the following (however, I will show an even more profitable way later):
We cross out the line corresponding to the profitable vector, and the remaining elements are summarized:
Profitable vector O1
Profitable vector O2
Profitable vector O3
And so on to O5, and immediately afterwards we calculate the sum of the elements in each vector:
We find the largest number of the sums - 18, so the O2 vector will be optimal and it contains the solution.
Consider the algorithm for how to get this solution. We find negative elements in this vector and summarize them, in our case, just -2. If we multiply by minus one, change the sign, we get the difference. The difference between the number for the largest combination and the answer we need to find, if simple, is x + r = y. x is either the sum of all elements divided by 2, or just the number from the largest combination. We substitute in the formula, we get 8 + 2 = 10. This will be the numerical solution of the matrix. However, we need to know exactly the vertices (workers) that make up the combination. Just take the column numbers for all positive numbers of the O2 vector: 1,3,4,5. This combination is the desired one.
Why we were looking for the maximum element (5) - if suddenly the solution is less than this element, then the combination will correspond to this element, and not the combination in the vector O.
There is a way to quickly determine the desired combination, without O vectors, but it is important for me that you pay attention to the resulting matrix of O vectors, if all its elements are added, we get the sum of all combinations (in this case 64, you can check it using the formula above). Thus, the matrix is the matrix of all combinations of the graph (workers). The way, for example, for a graph of size 20x20, the number of combinations is 1048575 and they all fit into this matrix of 20 orders, and the optimal solution is found, it is simply amazing!
And now let's solve this problem a bit faster:
1. We write out the sum of all elements and the maximum number.
2. Here B is useful to us, each element is subtracted from the sum of all elements, and the most favorable answer is determined by the advantageous vector.
Following the example of O2: 16 - (- 2) = 18. We have significantly reduced the execution time of the algorithm.
3. Further in the same way as previously we obtain the vector O2 and find the solution.
The number of steps does not exceed the second degree polynomial, you can see for yourself.
Some screenshots from the verification program:
4x4 matrix, decomposition and enumeration method
Matrix 50x50, 0.039 sec. on the decision
Matrix 100x100, 0.069 sec. on the decision
How are things going with other tasks? With the task of a traveling salesman things are good, but not very. For example, if we obtain the matrix of vectors O and the matrix of vectors O for the transposed matrix, then again we will get the matrix of all combinations, but here we have the combinations of Hamiltonian cycles:
In fact, I have not fully understood the task of the traveling salesman, but for the graph n = 4 it works, and for graphs n> 4 it does not work, because I need to rearrange the matrix of combinations a bit before I understand how.
This algorithm can actually help in many planning tasks, such as, for example, the same task of selecting employees for the task of efficiency, ideal training programs, nutrition, in principle, the application is unlimited.
The matrix of combinations is a thing that is not completely known to me and I would be glad if you could help to understand what it is and how to work with it.
Upd: finding the most clicks on this algorithm:
-2 - to designate that the vertices are not connected, 1 - that are connected, in the graph from the picture just 5 clicks and the maximum click - 1,2,3,4. The principle of finding a clique is the same.
Source: https://habr.com/ru/post/304616/
All Articles