Ladner's theorem

The NP-intermediate is a set of the theoretical computer science that deals with the structure of the complexity class NP in terms of P is concerned. It was proven by Richard Ladner in 1975 .

The class includes the complexity class of the languages deterministically decidable in polynomial time . The question of whether is a true subset of is still open (see P-NP problem ). The NP-complete problems are the most difficult problems in . The question whether there are problems in that are neither -complete nor lie in is answered in the affirmative by Ladner's theorem, if it holds. The set of these problems is called NP-intermediate or . ${\displaystyle \mathbf {NP} }$ ${\displaystyle \mathbf {P} }$ ${\displaystyle \mathbf {P} }$ ${\displaystyle \mathbf {NP} }$ ${\displaystyle \mathbf {NP} }$ ${\displaystyle \mathbf {NP} }$ ${\displaystyle \mathbf {NP} }$ ${\displaystyle \mathbf {P} }$ ${\displaystyle \mathbf {P} \neq \mathbf {NP} }$ ${\displaystyle \mathbf {NPI} }$

The set is so formal: . ${\displaystyle \mathbf {P} \neq \mathbf {NP} \;\Rightarrow \;\mathbf {NPI} \neq \emptyset }$

For the proof of the theorem, Ladner generated an artificial problem which has no practical relevance. It is not known if there are also natural problems (if any ). However, it is believed that the z. B. applies to the prime factorization . ${\displaystyle \mathbf {NPI} }$ ${\displaystyle \mathbf {P} \neq \mathbf {NP} }$

The theorem can be generalized so that it holds regardless of the assumption : ${\displaystyle \mathbf {P} \neq \mathbf {NP} }$

Under polynomial time reduction (both Turing reduction and many-one reduction) there is no minimal class over . ${\displaystyle \mathbf {P} }$

That means, if a problem is really more serious than the problems in , then there are problems that are also not in , but are really easier than . ${\displaystyle A}$ ${\displaystyle \mathbf {P} }$ ${\displaystyle B}$ ${\displaystyle \mathbf {P} }$ ${\displaystyle A}$

Evidence sketch

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

Be given a decidable language . On the condition one can choose. One defines a language that is reducible to polynomial time, but is not in : (under many-one reduction) and (under Turing reduction). Let be an enumeration of all Turing machines , each one additionally counting the number of steps and the -th machine holding on input at the latest after time . Let be a listing of the same time-limited oracle-Turing machines with oracles . Then there are two requirements for all machines that must be met: ${\displaystyle A\notin \mathbf {P} }$ ${\displaystyle \mathbf {P} \neq \mathbf {NP} }$ ${\displaystyle A=\mathrm {SAT} }$ ${\displaystyle B\notin \mathbf {P} }$ ${\displaystyle A}$ ${\displaystyle \mathbf {P} }$ ${\displaystyle B\leq _{\mathrm {P} }A}$ ${\displaystyle A\not \leq _{\mathrm {P} }B}$ ${\displaystyle T_{1},T_{2},\dotsc }$ ${\displaystyle e}$ ${\displaystyle x}$ ${\displaystyle \left|x\right|^{e}}$ ${\displaystyle T_{1}^{B},T_{2}^{B},\dotsc }$ ${\displaystyle B}$ ${\displaystyle T_{e},T_{e}^{B}}$ ${\displaystyle B}$

• ${\displaystyle R_{2e}:}$The language is unequal to the set of words that are accepted less in time . ${\displaystyle B}$ ${\displaystyle T_{e}}$ ${\displaystyle n^{e}}$

Formal: with time limit ${\displaystyle B\neq {\mathcal {L}}(T_{e})}$ ${\displaystyle n^{e}}$

• ${\displaystyle R_{2e+1}:}$The oracle machine does not describe a Turing reduction from to , which can be calculated smaller in time . ${\displaystyle T_{e}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n^{e}}$

Formal: with time limit ${\displaystyle A\neq {\mathcal {L}}(T_{e}^{B})}$ ${\displaystyle n^{e}}$

Since every Turing machine (e.g. by adding redundant states) occurs infinitely often in the enumeration , it is when it satisfies all . Similarly, if all apply, there is no polynomial time reduction from to . ${\displaystyle T_{1},T_{2},\dotsc }$ ${\displaystyle B\notin \mathbf {P} }$ ${\displaystyle R_{2e}}$ ${\displaystyle R_{2e+1}}$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle B}$now arises from by removing sufficiently large sections from so that it cannot be reduced to polynomial , but is still not in P. A polynomial calculable function is defined for the construction, which indicates for each step of the construction which requirement is being pursued. Then are exactly the elements in , so that in step a requirement of the mold was monitored: . Thus, the following function can be used to reduce polynomial to many-one: ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle g}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle B}$ ${\displaystyle \left|x\right|}$ ${\displaystyle 2e}$ ${\displaystyle B=\{x\in A\,\,|\,\,g(\left|x\right|){\text{ gerade}}\}}$ ${\displaystyle B}$ ${\displaystyle f}$ ${\displaystyle A}$

${\displaystyle f(x)={\begin{cases}x,&{\text{wenn }}g(\left|x\right|){\text{ gerade}}\\a,&{\text{sonst}}\end{cases}}}$

where is any element. ${\displaystyle a\notin A}$

The first requirement is chosen. For is defined inductive in such a way that it can be calculated in polynomial time. You start to calculate the values one after the other and stop after the calculation steps. be the largest number so that it can be determined in steps. Then there are two cases: ${\displaystyle g(0)=0}$ ${\displaystyle s>0}$ ${\displaystyle g(s)}$ ${\displaystyle g(0),g(1),\dots ,g(s-1)}$ ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle g(n)}$ ${\displaystyle s}$

• ${\displaystyle g(n)=2e}$: One looks for a word with . Since it should be possible to calculate polynomial in , only the first calculation steps of the search are carried out. ${\displaystyle z}$ ${\displaystyle B(z)\neq T_{e}(z)}$ ${\displaystyle g}$ ${\displaystyle s}$ ${\displaystyle s}$
  • If one is found, it is fulfilled. Then is . ${\displaystyle z}$ ${\displaystyle R_{2e}}$ ${\displaystyle g(s)=g(n)+1=2e+1}$
  • Otherwise it is not known whether it has already been fulfilled and in order to continue trying to fulfill. ${\displaystyle R_{2e}}$ ${\displaystyle g(s)=g(n)}$ ${\displaystyle R_{2e}}$
• ${\displaystyle g(n)=2e+1}$: One looks for a word with . Analogous to , only steps are carried out. ${\displaystyle z}$ ${\displaystyle A(z)\neq T_{e}^{B}(z)}$ ${\displaystyle 2e}$ ${\displaystyle s}$
  • One finds one , is fulfilled and . ${\displaystyle z}$ ${\displaystyle R_{2e+1}}$ ${\displaystyle g(s)=g(n)+1=2(e+1)}$
  • Otherwise it is not known whether it has already been fulfilled and in order to continue trying to fulfill. ${\displaystyle R_{2e+1}}$ ${\displaystyle g(s)=g(n)}$ ${\displaystyle R_{2e+1}}$

It must now be shown that all requirements are met. To do this, it suffices to show that is surjective . Suppose there is one with for everyone . Is would be polynomially decidable, although it only differs from on a finite number of words . Is , would be finite. But since it is not in , it cannot be reduced to a finite language. ${\displaystyle g}$ ${\displaystyle n}$ ${\displaystyle g(n)=g(m)}$ ${\displaystyle m>n}$ ${\displaystyle g(n)=R_{2e}}$ ${\displaystyle B}$ ${\displaystyle A\notin \mathbf {P} }$ ${\displaystyle g(n)=R_{2e+1}}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle \mathbf {P} }$

literature

• Sanjeev Arora and Boaz Barak: Computational Complexity. A modern approach . Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4 .
• Ladner, Richard: On the Structure of Polynomial Time Reducibility . Journal of the ACM (JACM) 22 (1): 155-171, 1975.
• Piergiorgio Odifreddi : Classical Recursion Theory, Volume II . Elsevier, 1999. ISBN 0-444-50205-X

Web links

• Lance Fortnow: Two Proofs of Ladner's Theorem (PDF file; 72 kB)

Individual evidence

1. ↑ ^{a b} Odifreddi 1999, p. 191