P versus NP problem

The precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures"[3] (and independently by Leonid Levin in 1973[4]).

In 1955, mathematician John Nash wrote a letter to the NSA, speculating that cracking a sufficiently complex code would require time exponential in the length of the key.

[5] If proved (and Nash was suitably skeptical), this would imply what is now called P ≠ NP, since a proposed key can be verified in polynomial time.

Another mention of the underlying problem occurred in a 1956 letter written by Kurt Gödel to John von Neumann.

Gödel asked whether theorem-proving (now known to be co-NP-complete) could be solved in quadratic or linear time,[6] and pointed out one of the most important consequences—that if so, then the discovery of mathematical proofs could be automated.

As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP.

Fischer and Rabin proved in 1974[17] that every algorithm that decides the truth of Presburger statements of length n has a runtime of at least

A theoretical polynomial algorithm may have extremely large constant factors or exponents, rendering it impractical.

It is also intuitively argued that the existence of problems that are hard to solve but whose solutions are easy to verify matches real-world experience.

For example, in 2002 these statements were made:[8] The main argument in favor of P ≠ NP is the total lack of fundamental progress in the area of exhaustive search.

[...] The resolution of Fermat's Last Theorem also shows that very simple questions may be settled only by very deep theories.Being attached to a speculation is not a good guide to research planning.

Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required.When one substitutes "linear time on a multitape Turing machine" for "polynomial time" in the definitions of P and NP, one obtains the classes DLIN and NLIN.

The potential consequences, both positive and negative, arise since various NP-complete problems are fundamental in many fields.

Gödel, in his early thoughts on computational complexity, noted that a mechanical method that could solve any problem would revolutionize mathematics:[36][37] If there really were a machine with φ(n) ∼ k⋅n (or even ∼ k⋅n2), this would have consequences of the greatest importance.

Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine.

For example, it is possible that SAT requires exponential time in the worst case, but that almost all randomly selected instances of it are efficiently solvable.

Russell Impagliazzo has described five hypothetical "worlds" that could result from different possible resolutions to the average-case complexity question.

In particular, some of the most fruitful research related to the P = NP problem has been in showing that existing proof techniques are insufficient for answering the question, suggesting novel technical approaches are required.

These barriers lead some computer scientists to suggest the P versus NP problem may be independent of standard axiom systems like ZFC (cannot be proved or disproved within them).

[46] Therefore, assuming (as most complexity theorists do) some NP problems don't have efficient algorithms, proofs of independence with those techniques are impossible.

The P = NP problem can be restated as certain classes of logical statements, as a result of work in descriptive complexity.

Consider all languages of finite structures with a fixed signature including a linear order relation.

As long as the signature contains at least one predicate or function in addition to the distinguished order relation, so that the amount of space taken to store such finite structures is actually polynomial in the number of elements in the structure, this precisely characterizes P. Similarly, NP is the set of languages expressible in existential second-order logic—that is, second-order logic restricted to exclude universal quantification over relations, functions, and subsets.

If there is an algorithm (say a Turing machine, or a computer program with unbounded memory) that produces the correct answer for any input string of length n in at most cnk steps, where k and c are constants independent of the input string, then we say that the problem can be solved in polynomial time and we place it in the class P. Formally, P is the set of languages that can be decided by a deterministic polynomial-time Turing machine.

Formally, NP is the set of languages with a finite alphabet and verifier that runs in polynomial time.

The following defines a "verifier": Let L be a language over a finite alphabet, Σ. L ∈ NP if, and only if, there exists a binary relation

It can be shown that COMPOSITE ∈ NP by verifying that it satisfies the above definition (if we identify natural numbers with their binary representations).

While the P versus NP problem is generally considered unsolved,[49] many amateur and some professional researchers have claimed solutions.

The film Travelling Salesman, by director Timothy Lanzone, is the story of four mathematicians hired by the US government to solve the P versus NP problem.

[52] In the sixth episode of The Simpsons' seventh season "Treehouse of Horror VI", the equation P = NP is seen shortly after Homer accidentally stumbles into the "third dimension".