P-NP problem

The P - NP problem (also P≟NP , P versus NP ) is an unsolved problem in mathematics , especially in complexity theory in theoretical computer science . The question is whether the set of all problems that can be solved quickly ( ) and the set of all problems for which a proposed solution can be quickly checked for correctness ( ) are identical. ${\ displaystyle P}$ ${\ displaystyle NP}$

It is clear that you can quickly check the correctness of a solution for all problems that can be solved quickly , but the reverse is not clear: for some problems there is an algorithm that can quickly check a proposed solution , but it could neither an algorithm could be found that would quickly find a correct solution, nor could the impossibility of such an algorithm be proven. Thus the question is unsolved. If one were to find an algorithm for all quickly testable problems that also solves them quickly , then this would apply . If it could be shown for at least one problem that it cannot be solved quickly in principle , it would be proven. ${\ displaystyle NP}$ ${\ displaystyle P = NP}$ ${\ displaystyle NP}$ ${\ displaystyle P \ neq NP}$

In this context, a problem is considered to be quick to solve or a solution to be quick to test if an algorithm exists in which the increase in the computational effort (number of calculation steps) is limited by a polynomial function as the input increases, and this increase does not run exponentially . Put simply, the size of the input is the number of elements that are entered into the algorithm. For a problem such as sorting index cards, this would be the number of index cards.

history

The problem was recognized at the beginning of the 1970s due to independent work by Stephen Cook and Leonid Levin .

The P-NP problem is considered to be one of the most important unsolved problems in computer science and was added to the list of Millennium Problems by the Clay Mathematics Institute .

As later became known, the problem can already be formulated in a letter from Kurt Gödel , which the latter sent to John von Neumann shortly before his death (on March 20, 1956). Another early formulation is found in a 1955 letter from John Forbes Nash to the National Security Agency on cryptography.

P and NP

The complexity class NP, assuming P ≠ NP. In this case, NP also contains problems above P that are not NP-complete .

Complexity theory classifies problems that computers can compute based on the amount of time or memory required to solve them, or more precisely, according to how quickly the effort grows with the size of the problem. One problem is, for example, sorting index cards. It can now be examined how the required time changes when a stack twice as high is sorted.

The measure used here for the computational effort is the number of computation steps that the algorithm needs for a problem ( time complexity ). In order to clearly indicate the calculation effort, formal machine models are also required to represent the solution algorithms. A frequently used model is the deterministic Turing machine , which can be viewed as the abstraction of a real computer.

P

One of the problem categories is the complexity class . It contains the problems for which a deterministic Turing machine exists that solves the problem in polynomial time . That means, there is a polynomial with , so that the Turing machine does not need more than calculation steps for any problem instance (with length of the input) . Problems from can thus be solved deterministically in polynomial time . ${\ displaystyle P}$ ${\ displaystyle f (n) = n ^ {k} + c}$ ${\ displaystyle c, k \ in \ mathbb {N}}$ ${\ displaystyle n}$ ${\ displaystyle f (n)}$ ${\ displaystyle P}$

The sorting problem mentioned above is in P because there are algorithms that sort a number of records (index cards) in a time that is bounded by a quadratic function in . Another example of a problem in FIG . 4 is the circuit evaluation problem . ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle P}$

The difference between a Turing machine and real computers does not matter here, because every algorithm that solves a problem in polynomial time on a real computer can also be implemented with a Turing machine in polynomial time (although the degree of the polynomial limiting the runtime is in the Usually will be higher).

NP

Another machine model is the nondeterministic Turing machine (NTM), it is a generalization of the deterministic variant. In a situation, an NTM can have several options for continuing its calculation, so the calculation method is not always clearly determined. It is a theoretical model; there are no real computers that can branch out their calculation path in this way. Its usefulness in this context is that it can be used to define another complexity class that contains many problems of practical interest, of which one does not yet know whether they are in. ${\ displaystyle NP}$ ${\ displaystyle P}$

${\ displaystyle NP}$ is defined as the set of problems solvable by an NTM in polynomial time. The deterministic Turing machine is a special case of the NTM, it dispenses with branching the computation path. Therefore is a subset of . ${\ displaystyle P}$ ${\ displaystyle NP}$

One can define equivalently as the set of problems of which it can be decided in polynomial time with a deterministic Turing machine whether a proposed solution applies. For example, no deterministic algorithm is currently known for factoring a given number in polynomial time . However, it is very easy to check whether a proposed factor divides the number without a remainder and is therefore a factor of the number. ${\ displaystyle NP}$

Is P = NP?

Relationship of the problems in P and NP and the NP-difficult and NP-complete

It is not known whether the two classes and are identical, i.e. whether even the most difficult problems of the class can be efficiently solved with deterministic machines. In order to formally grasp the concept of the “most difficult problem in ”, the concepts of NP completeness and NP severity were introduced. A problem X is NP-hard if one can reduce every problem to X by polynomial time reduction . Should one find an NP-hard problem X that can be solved deterministically in polynomial time, one could also solve every problem in deterministically polynomial time by reducing it to X, and it would be shown. A problem that lies in and is NP-hard is called NP-complete. ${\ displaystyle P}$ ${\ displaystyle NP}$ ${\ displaystyle NP}$ ${\ displaystyle NP}$ ${\ displaystyle NP}$ ${\ displaystyle NP}$ ${\ displaystyle P = NP}$ ${\ displaystyle NP}$

An illustrative NP-complete problem is the rucksack problem : A container of a certain size should be filled with a selection from given objects in such a way that the contents are as valuable as possible without exceeding the capacity of the container. Another important example is the satisfiability problem of propositional logic .

It was also shown: if is and thus the NP-complete problems are not in , then there are also problems in which are neither NP-complete nor in , which represent an intermediate level in their difficulty. A candidate for such a problem is the graph isomorphism problem , of which up to now we neither know whether it lies in nor whether it is NP-complete. ${\ displaystyle P \ neq NP}$ ${\ displaystyle P}$ ${\ displaystyle NP}$ ${\ displaystyle P}$ ${\ displaystyle P}$

the solution of the problem

So far, only exponential time algorithms on deterministic computing machines are known for the exact solution of NP-complete problems. However, it has not been proven that there are no polynomial-time algorithms for the solution, in contrast to another class of problems that are guaranteed to require at least exponential running time ( EXPTIME -complete problems) and that are thus demonstrably outside the class . If one were to find an algorithm (class ) that was polynomially time-limited on deterministic computing machines for one of these NP-complete problems for all inputs , then any problem could be reduced to it by polynomial time reduction and thus solved in deterministic polynomial time; in this case it would be . ${\ displaystyle P}$ ${\ displaystyle P}$ ${\ displaystyle NP}$ ${\ displaystyle P = NP}$

Since it has not yet been possible to design such an algorithm, most experts assume that this is true. This could be proven mathematically by proving for a problem from the class that no deterministic polynomial time algorithm exists for its solution. ${\ displaystyle P \ neq NP}$ ${\ displaystyle NP}$

Possible scenarios for a solution to the problem would be

It is proven that .

{\ displaystyle P \ neq NP}

It is proven that is logically independent of ZFC . ${\ displaystyle P \ neq NP}$

It proves that by giving an efficient algorithm for an NP-complete problem . ${\ displaystyle P = NP}$

It is proven by means of non-constructive techniques that it holds, i.e. without constructing an explicit algorithm.

{\ displaystyle P = NP}

The complexity of the problem is supported by the fact that it has already been shown for various proof techniques that they alone are not sufficient to clarify the question.

Relative proof techniques

A proof of the relationship between two complexity classes is relativizing if the relationship is preserved for any oracles added . The class of relativising proof techniques includes e.g. B. also the method of diagonalization, which is often used in complexity theory . If one shows, for example, by means of diagonalization, then automatically applies to every oracle . The following important theorem by Theodore Baker, John Gill and Robert Solovay proves that relativising proof techniques cannot be an effective means for the P-NP problem and that many methods of attacking the P-NP problem from theoretical computer science fail as a result: ${\ displaystyle K \ neq K '}$ ${\ displaystyle K ^ {A} \ neq K '^ {A}}$ ${\ displaystyle A}$

There are two oracles and , so that and .

{\ displaystyle A}

{\ displaystyle B}

{\ displaystyle \ operatorname {P} ^ {A} = \ operatorname {NP} ^ {A}}

{\ displaystyle \ operatorname {P} ^ {B} \ neq \ operatorname {NP} ^ {B}}

Natural evidence

Alexander Razborov and Steven Rudich introduced the concept of "natural proofs" (Engl. Natural proofs ) in their same work from 1994. Under the general presumption that certain one-way functions exist, they showed that it is not possible to separate and through some sort of combinatorial proof technique. ${\ displaystyle P}$ ${\ displaystyle NP}$

In simple terms, a proof is “natural” if it defines a criterion for “simplicity” and shows that functions have this property and that there is an NP-complete problem that does not have this property. The criterion for “simplicity” must apply to a sufficiently large number of functions on the one hand and be sufficiently easy to check on the other. ${\ displaystyle P}$

Attempts to prove

While the P-NP problem is generally considered unsolved, many amateurs and professional researchers have published various solutions. Gerhard Woeginger runs a collection of attempted evidence, which in September 2016 lists 62 alleged evidence for , 50 evidence for , two evidence that the problem is undecidable, and one evidence that it is undecidable. Among all this work, there is only one that has appeared in a peer-reviewed journal that has been thoroughly reviewed by the experts in the field and whose correctness is accepted by the general research community: the work of Mihalis Yannakakis (And this paper clarifies not the P versus NP question, but "only" shows that a certain approach to clarifying this question will never work). ${\ displaystyle P = NP}$ ${\ displaystyle P \ neq NP}$

More recently, the attempted proof of August 6, 2010 by the mathematician Vinay Deolalikar employed at Hewlett-Packard has become known . It was quickly disproved, but it deserves the credit for having brought the subject into focus at times, both in public and in specialist circles. ${\ displaystyle P \ neq NP}$

Practical relevance

Many practically relevant problems are NP-complete. Solving the P-NP problem could therefore be of great importance. The proof of would mean that there are algorithms for the problems of the class which solve them in polynomial time. However, since no algorithm has been found in the past decades, despite an intensive search, that solves an NP-complete problem in polynomial time, it is doubted in the professional world that such algorithms even exist, i. H. one proceeds from. ${\ displaystyle P = NP}$ ${\ displaystyle NP}$ ${\ displaystyle P \ neq NP}$

Many NP-complete problems, such as the traveling salesman problem , the backpack problem or the problem of the coloring of graphs , could theoretically be optimally solved in a short time. However, the exponents and constants of the runtime function of a polynomial method could also be so high that one of the previously known solution methods, e.g. B. an approximate or probabilistic , is always the better. ${\ displaystyle P = NP}$

With the proof of , NP problems would finally be classified as difficult to solve. is currently the assumption of most scientists, and the proof would be less momentous than the proof of . ${\ displaystyle P \ neq NP}$ ${\ displaystyle P \ neq NP}$ ${\ displaystyle P = NP}$

In cryptology , unlike most other areas, complexity is a desirable property. The security of some asymmetrical encryption methods is based on this factor alone. An NP algorithm can break any asymmetrical cryptosystem by “guessing” the secret key and using the method that the actual recipient of the message would use to efficiently decrypt it and thus verify the key. So proof of would mean that there is a prospect of breaking these cryptosystems in practice. ${\ displaystyle P = NP}$

literature

Scott Aaronson : in: (ed.) John Forbes Nash, Michael Rassias, Open problems mathematics, Springer 2016, pp 1-122

{\ displaystyle P \; {\ stackrel {?} {=}} \; NP}

Stephen A. Cook : vs. problem , Clay Mathematics Institute (Millennium Problems) ${\ displaystyle P}$ ${\ displaystyle NP}$

Lance Fortnow : Status of the problem ${\ displaystyle P = NP}$ , Comm. ACM, Vol. 52, 2009, pp. 78-86, online

Lance Fortnow : The golden ticket. and the search for the impossible ${\ displaystyle P, NP}$ , Princeton University Press 2013

Richard J. Lipton: The Question and Gödel's Lost Letter ${\ displaystyle P = NP}$ , Springer 2010

Individual evidence

^ John Dawson Kurt Gödel - Leben und Werk , Springer Verlag 1997, p. 177, there the letter is quoted

^ Janis Hartmanis Gödel, von Neumann and the P? = NP Problem , Bulletin European Assoc. Theor. Computer Science, 38, 1989, pp. 101-107

^ The Gödel Letter, Lipton's blog , with English translation

↑ Michael Sipser The history and the status of the P versus NP Question , 24th STOC Proc., 1992, pp. 603-618

↑ Scott Aaronson, P =? NP, in: Nash, Rassias, Open problems in Mathematics, Springer 2016, p. 1 (with a quote from the letter)

↑ National Cryptologic Museum Opens New Exhibit on Dr. John Nash , NSA 2012. The passage on p. 4 of the 1955 letter reads: Now my general conjecture is as follows: for almost all sufficiently complex types of enciphering, especially where the instructions given by different portions of the key interact complexly with each other in the determination of their ultimate effects on the enciphering, the mean key computation length increases exponentially with the length of the key, or in other words, the information content of the key. The significance of this general conjecture, assuming its truth, is easy to see. It means that it is quite feasible to design ciphers that are effectively unbreakable. .... The nature of this conjecture is such that I cannot prove it, even for a special type of ciphers. Nor do I expect it to be proven.

^ Richard E. Ladner: On the structure of polynomial time reducibility. In: Journal of the ACM. 22, No. 1, 1975, pp. 151-171 ( doi: 10.1145 / 321864.321877 ).

↑ Donald Knuth considers this variant to be correct, see the argumentation and interpretation in Twenty Questions for Donald Knuth, May 2014 , question 17.

^ Theodore Baker, John Gill, Robert Solovay: Relativizations of the P =? NP question. In: SIAM Journal on Computing. 4, No. 4, 1975, pp. 431-442, 1975 ( doi: 10.1137 / 0204037 ).

↑ Gerhard Woeginger: P versus NP page. September 26, 2016, accessed April 3, 2020 .

↑ Newsticker Heise 2010

↑ Alexander Nazaryan: A Most Profound Math Problem . In: The New Yorker . May 2, 2013. Retrieved February 15, 2017.

↑ His blog on this with the article in a revised version.

Web links

"The P-versus-NP page" : A collection of links to scientific articles and attempted solutions to the P-NP problem by Gerhard Woeginger (English)

[1] John Dawson Kurt Gödel - Leben und Werk , Springer Verlag 1997, p. 177, there the letter is quoted

[2] Janis Hartmanis Gödel, von Neumann and the P? = NP Problem , Bulletin European Assoc. Theor. Computer Science, 38, 1989, pp. 101-107

[3] The Gödel Letter, Lipton's blog , with English translation

[4] Michael Sipser The history and the status of the P versus NP Question , 24th STOC Proc., 1992, pp. 603-618

[5] Scott Aaronson, P =? NP, in: Nash, Rassias, Open problems in Mathematics, Springer 2016, p. 1 (with a quote from the letter)

[6] National Cryptologic Museum Opens New Exhibit on Dr. John Nash , NSA 2012. The passage on p. 4 of the 1955 letter reads: Now my general conjecture is as follows: for almost all sufficiently complex types of enciphering, especially where the instructions given by different portions of the key interact complexly with each other in the determination of their ultimate effects on the enciphering, the mean key computation length increases exponentially with the length of the key, or in other words, the information content of the key. The significance of this general conjecture, assuming its truth, is easy to see. It means that it is quite feasible to design ciphers that are effectively unbreakable. .... The nature of this conjecture is such that I cannot prove it, even for a special type of ciphers. Nor do I expect it to be proven.

[7] Richard E. Ladner: On the structure of polynomial time reducibility. In: Journal of the ACM. 22, No. 1, 1975, pp. 151-171 ( doi: 10.1145 / 321864.321877 ).