P versus NP problem

The P- NP problem (also ≟ P NP, P versus NP) is an unsolved problem in mathematics and theoretical computer science, especially in complexity theory. This raises the question of what relationship the two complexity classes P and NP are. The problem was detected at the beginning of the 1970s due independently successful work of Stephen Cook and Leonid Levin.

The P- NP problem is one of the important unsolved problems in computer science and was taken up by the Clay Mathematics Institute's list of the Millennium problems.

As it became known later, finds itself a formulation of the problem in a letter from Kurt Gödel, the shortly before his death that John von Neumann sent ( March 20, 1956).

• 2.1 relativizing proof techniques
• 2.2 Natural evidence

P and NP

Complexity theory classifies problems that can be computed by computers, based on the effort required for their solution. A way to quantify the computational effort of an algorithm, the maximum number of necessary computational steps, the time complexity. The complexity of a problem is then the complexity of the best algorithm which solves this problem; Here, it is always ( hereinafter referred to as n ) in relation to the length of the input provided for the calculation. For precise analysis of the time complexity also formal models of machines are needed. A model commonly used is the deterministic Turing machine, which can be regarded as the abstraction of a real computer.

P

One of the complexity theoretic problem categories is the complexity class P. For each problem in this class there is a deterministic Turing machine ( with an algorithm, a " programming" ), which solves the problem and of a polynomial of the form ( which is a constant) can be specified, which limited the time complexity of solving in relation to the input length to the top. Problems in P are thus deterministically in polynomial time solvable.

Examples of problems of complexity class P are the sorting problem or the circuit evaluation problem.

EXP

A further defined on the basis of the deterministic Turing machine problem set is the complexity class EXP. Instead of a polynomial can be specified here as the upper limit for the time complexity is only a function of the mold as a function of the input length. The solution of the hardest problems in this class so requires exponential time. Furthermore, the class P is completely contained in EXP: Every problem can be solved in a polynomial time requirement remains (for large n ) and below an exponential time requirement.

For some problems in EXP but it can be shown that this can not be solved in polynomial time, such as the question of whether a Turing machine on an input of size size stops within steps or not - the so-called halting problem. The solvability of these problems can not be significantly improved by the current state of knowledge by future technological advances.

That said there are problems in EXP, the solution time requirements have an exponential upper bound, but can be described not guaranteed by polynomial bound.

NP

However, the complexity theory defines other machine models in addition to the deterministic Turing machine. An important model is the non-deterministic Turing machine, which is an extension of the deterministic variant. A non-deterministic Turing machine potentially has multiple ways to continue at any moment their calculation, the calculation method is therefore not clearly determined. It is a theoretical model, which is not equivalent to current computers. Its usefulness is in this context that by non-deterministic Turing machines another complexity class can be distinguished, which is within EXP and includes turn P.

The complexity class NP is the set of all separable from non-deterministic Turing machine in polynomial time problems. This subset of EXP contains a very large number of relevant issues. This naturally leave the problems of P also non-deterministic polynomial- solve, P is a subset of NP.

If P = NP?

It is unclear whether the two classes P and NP are identical, and thus whether the class NP the most serious problems just as efficient as the complexity class P can be solved. In order to grasp the concept of the " most serious problem in NP " formally, the concept of NP-hardness has been introduced. A problem is NP- hard if its resolution would allow ( in polynomial time ) the solution to every other problem in NP in polynomial time (using a deterministic machine; Polynomialzeitreduktion ). A problem is in NP and is NP-hard ie, NP -complete.

An illustrative problem of NP for which it is not clear whether it is contained in P, is the knapsack problem. In this problem a container is to be filled with a certain size as predetermined objects that the container is filled up and the contents of only be as valuable as possible. Another important example is the satisfiability problem of propositional logic.

Solution of the problem

So far for the exact solving NP- complete problems are known only Exponentialzeitalgorithmen on deterministic computing machines. Other classes of problems which require guaranteed at least exponential running time, illustrate the presently practical insolubility of NP- complete problems.

In contrast to these problems, which are above the class NP is no proof for NP- complete problems because of the open P -NP problem that an optimal algorithm requires exponential run time. If one were to find a deterministic polynomial time bounded algorithm computing machines for any of these problems, so any problem can be reduced to that of NP by Polynomialzeitreduktion and thus solved in deterministic polynomial time; in this case would be P = NP.

Since it has not yet succeeded in designing such an algorithm, assumes most of the experts that P ≠ NP. This could be mathematically proven fact that is demonstrated for a problem from the class NP, no polynomial time algorithm exists deterministic to its solution.

Possible scenarios would be for a solution of the problem

• It is proved that P ≠ NP.
• It is proved that P ≠ NP is logically independent of ZFC.
• It is proved that P = NP by an efficient algorithm is given for an NP-complete problem.
• It is proved by means of non - constructive techniques that P = NP, ie to construct without an explicit algorithm.

For the difficulty of the problem is the fact that has already been shown for various proof techniques that they are not alone sufficient to resolve the issue.

Relativizing proof techniques

A proof of the relationship between two complexity classes relativized if the relationship is maintained for any added oracle. Under the class of relativizing proof techniques falls, for example, a commonly used in complexity theory method of diagonalization. If you point example by means of diagonalization, so automatically applies to any oracle. The next important set of Theodore Baker, John Gill, and Robert Solovay proves that relativizing proof techniques can be not an effective means for the P - NP problem and fail many methods of attack on the P- NP problem in theoretical computer science this way:

Natural evidence

Alexander Alexandrovich Rasborow and Steven Rudich introduced the concept of "natural proofs" (Natural proofs ) in their eponymous work of 1994. Under the general assumption suspected that certain one-way functions exist, they showed that it is not possible to separate P and NP by a certain type of combinatorial proof techniques.

Simply put, is a proof " of course " when he defined a criterion of "simplicity" and shows that functions of P have this property and there is an NP -complete problem, which does not have this property. The criterion for " simplicity " must here apply to one for sufficiently large set of functions, on the other hand be sufficiently simple verifiable.

Proof attempts

On 6 August 2010, the employees at Hewlett -Packard mathematician Vinay Deolalikar sent a possible proof for P ≠ NP at different researchers. Two days later appeared on the pre-release version of the proof on the web. After a few days claiming Neil Immerman to have found two fatal flaws in the evidence. The proof attempt has been much discussed because of its interesting approach among complexity theorists.

Practical Relevance

Many also practically relevant problems are NP -complete. The solution of the problem could therefore be of great importance. The proof of P = NP would imply that for problems of the former class NP algorithms exist that a solution - can generate polynomial time - much faster. Since it is not yet succeeded in the past decades, only to find a single such algorithm is doubted in the art that these algorithms exist at all.

Many practical applications for NP- complete problems such as the problem of the traveling salesman, the knapsack problem or the problem of coloring of graphs would, in the case of P = NP theoretically optimal in a short time solvable. However, the exponents and constants could also be so high in a polynomial solution is that for practically relevant applications an exponential solution method is still the better.

With the proof of P ≠ NP NP problems would be definitively classified as difficult to solve. P ≠ NP currently corresponds to the assumption of most scientists, and the proof would be less severe than the proof of P = NP.

In Cryptology complexity is a desired property, in contrast to most other areas. The safety of some asymmetric encryption scheme is based solely on this factor. An NP algorithm can break any asymmetric crypto system by " guessing " the secret key and the method would use the actual recipient of the message, decrypt, or verify efficiently.