NP-intermediate

The set of Ladner is a set of theoretical computer science that deals with the structure of the complexity class NP. It was proved in 1975 by Richard Ladner.

The class NP includes the complexity class P of polynomial time deterministically decidable languages. The question of whether P is a proper subset of NP, is still open ( P- NP problem ). The so-called NP -complete problems are the hardest problems in NP. The question whether problems exist in NP that are neither NP- complete nor lie in P is positively answered by the set of Ladner, if P ≠ NP. The amount of these problems is called NP -intermediate or NPI.

The set is so formal.

For the proof of the theorem an artificial problem was generated by Ladner, which has no practical relevance. It is not known whether "natural" problems in the NPI are ( assuming P ≠ NP). However, it is believed that this example applies to the prime factorization.

The theorem can be generalized as follows, so that it applies regardless of the assumption P ≠ NP:

That is, if a problem is really serious than the problems, then there are problems that also are not in, but really lighter than.

Sketch of proof

This evidence, which also covers the first specified generalization, essentially follows Odifreddi in 1999 and is based on Ladner 's original proof. An alternative proof, in the SAT is gepaddet is described by Arora and Barak 2009.

Be given a decidable language. Assuming you can choose. We define a language that is polynomial time reducible to, but not in P: ( under many-one reduction) and ( under Turing reduction). Is a list of all Turing machines, each including the number of the counting steps, and keeps the input -th machine at least according to time. Be a list of time-limited in the same way oracle Turing machine with oracle. Then there are two machines for all requirements that must be met:

  • The language is not the same set of words, which takes less time to.
  • The oracle machine describes no Turing reduction, which can be computed in less time.

Since each Turing machine infinitely often in the enumeration to occur ( for example by adding redundant states), is when it all fulfilled. Similarly, there are, if any apply, no Polynomzeitreduktion from to.

Arises from now, by sufficiently large portions are removed from, so can not be reduced polynomially to, but still is not yet in P. To construct a polynomially computable function is defined that specifies for each step x of the design, which request is being tracked. Then there are precisely those elements in, so a requirement of the form was followed in step. Thus can be reduced using the following polynomial function on many-one:

Wherein any one element.

The first requirement is chosen. For the following is inductively defined so that it can be calculated in polynomial time. One begins to sequentially compute the values ​​and stops after calculating steps from. is the largest number so that you can determine in steps. Then there are two cases:

  • : Man looking through a word. Since polynomial in predictable supposed to be, only the first calculation steps of the search are performed. If it found one, is satisfied. Then is.
  • Otherwise, it is not known whether it has been already fulfilled and to continue to try to meet.
  • Find a one, is satisfied and.
  • Otherwise, it is not known whether it has been already fulfilled and to continue to try to meet.

We have to show now that all requirements are met. For this purpose, it is enough to show that is surjective. Suppose there is a with for all. Is would be polynomially decidable, although it differs only on a finite number of words. Is would be finite. However, since is not in P, it can not be reduced to a finite language.

495155
de