P = NP? The most important unsolved problem of theoretical informatics

    This task was formulated in 1971 and still remains unresolved. For proof of the statement P = NP proof or refutation of his Clay Mathematics Institute appointed prize of 1 million US dollars. If, nevertheless, it turns out that P = NP, then this will make it possible to quickly and efficiently solve many currently unsolvable problems.

    So what is the essence of the problem?



    The concepts of complexity classes P and NP are studied by the theory of computational complexity. Class P ( P olynomial time) includes simple tasks that can be solved in polynomial time with respect to the input length. An example of such a task is array sorting.. 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 algorithms belonging to the class P lies in the fact that with increasing input length, the execution time increases slightly.

    The class NP ( N on-deterministic P olynomial time) includes tasks for which the solution can be verified in polynomial time. Note that this is only about checking an already found solution. The complexity of the tasks of this class lies in the fact that directly finding a solution requires significantly more than polynomial time. Consider as an examplethe problem of the sum of the subsets . It is formulated as follows: "in a given set of integers, is there at least one nonempty subset of whose sum of elements is equal to zero?" For example, let us be given the set {5, -2, 17, 10, -4, -8}. For him, the answer to the question is “ 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 add up the elements of the found subset). But exponential time must be spent on finding a solution, since it is necessary to check all possible subsets. The number of possible combinations is 2 n for input of length n. This makes the solution of 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 NP algorithms in polynomial time. If this is proved, for example, for the above problem of 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, we can say that although the question of the equality of the classes P and NP has not yet been resolved, many experts are inclined to believe that they are not equal. In support of this opinion, it is argued that for more than three and a half decades no algorithm has been found with polynomial execution time for any of the 3000 known NP-complete tasks . But finally, a rigorous mathematical proof will put a point in the dispute.

    Also popular now: