P = NP? The most important unsolved problem of theoretical informatics
This task was formulated in 1971 and still remains unsolved. For the proof of the statement P = NP or for the proof of his refutation, the Clay Mathematical Institute awarded a prize of $ 1 million. If, nevertheless, it turns out that P = NP, then this will make it possible to quickly and effectively solve many intractable problems at the moment.
So what is the essence of the problem?
')
The concepts of complexity classes P and NP are studied by the theory of complexity of computations. The class P ( P olynomial time) includes simple tasks that can be solved in polynomial time with respect to the length of the input. An example of such a task is the sorting of an array . Depending on the selected sorting algorithm, for an array of length n, the number of operations performed will be from O (n * log (n)) to O (n 2 ). Thus, the simplicity of the algorithms belonging to the class P is that with an increase in the length of the input, the execution time increases slightly.
The class NP ( N on-deterministic P olynomial time) includes tasks for which solution verification can be performed in polynomial time. Notice that this is only a verification of the solution already found . The complexity of the tasks of this class lies in the fact that directly finding a solution requires much more than polynomial time. Consider as an example the problem of the sum of subsets . It is formulated as follows: “In a given set of integers, is there at least one non-empty subset whose sum of elements equals zero?” For example, suppose we are given the set {5, -2, 17, 10, -4, -8}. For him, the answer to the question " yes ", because the desired subset exists: -2 + 10-8 = 0. It is easy to make sure that the solution is checked quickly (you just need to sum the elements of the found subset). But it is necessary to spend exponential time on finding a solution, since it is necessary to check all possible subsets. The number of possible combinations is 2 n for input length n. This makes solving the problem posed impractical for large values of n.
So, we return directly to the problem P = NP. A positive answer will mean that it is possible to execute the NP algorithms in polynomial time. If this is proved, for example, for the above problem on the sum of subsets, then the same will be true for many other complex problems. The fact is that there is a special class of NP algorithms, called NP-complete for which it is proved that any task belonging to it can be easily reduced to any other task of this class. Here is a list of some well-known NP-complete tasks:
In conclusion, it can be said that although the question of the equality of the classes P and NP is still not resolved, many experts are inclined to believe that they are not equal. In support of this view, it is argued that for more than three and a half decades, no algorithm has been found with polynomial execution times for any of the 3000 known NP-complete problems . But finally a rigorous mathematical proof will put an end to the dispute.
So what is the essence of the problem?
')
The concepts of complexity classes P and NP are studied by the theory of complexity of computations. The class P ( P olynomial time) includes simple tasks that can be solved in polynomial time with respect to the length of the input. An example of such a task is the sorting of an array . Depending on the selected sorting algorithm, for an array of length n, the number of operations performed will be from O (n * log (n)) to O (n 2 ). Thus, the simplicity of the algorithms belonging to the class P is that with an increase in the length of the input, the execution time increases slightly.
The class NP ( N on-deterministic P olynomial time) includes tasks for which solution verification can be performed in polynomial time. Notice that this is only a verification of the solution already found . The complexity of the tasks of this class lies in the fact that directly finding a solution requires much more than polynomial time. Consider as an example the problem of the sum of subsets . It is formulated as follows: “In a given set of integers, is there at least one non-empty subset whose sum of elements equals zero?” For example, suppose we are given the set {5, -2, 17, 10, -4, -8}. For him, the answer to the question " yes ", because the desired subset exists: -2 + 10-8 = 0. It is easy to make sure that the solution is checked quickly (you just need to sum the elements of the found subset). But it is necessary to spend exponential time on finding a solution, since it is necessary to check all possible subsets. The number of possible combinations is 2 n for input length n. This makes solving the problem posed impractical for large values of n.
So, we return directly to the problem P = NP. A positive answer will mean that it is possible to execute the NP algorithms in polynomial time. If this is proved, for example, for the above problem on the sum of subsets, then the same will be true for many other complex problems. The fact is that there is a special class of NP algorithms, called NP-complete for which it is proved that any task belonging to it can be easily reduced to any other task of this class. Here is a list of some well-known NP-complete tasks:
- Traveling salesman task
- The task of the sum of subsets
- The task of satisfying the boolean formula
- Graph coloring problem
- Backpack problem
In conclusion, it can be said that although the question of the equality of the classes P and NP is still not resolved, many experts are inclined to believe that they are not equal. In support of this view, it is argued that for more than three and a half decades, no algorithm has been found with polynomial execution times for any of the 3000 known NP-complete problems . But finally a rigorous mathematical proof will put an end to the dispute.
Source: https://habr.com/ru/post/43224/
All Articles