Borodin's theorem of gaps

The gap theorem is a 1972 by Allan Borodin published set of computational complexity in the theoretical computer science .

The theorem was proven by Boris Trakhtenbrot as early as 1964 , but this was ignored in the West.

It says that there are gaps of any size in the hierarchy of complexity classes .

Formal: For total, calculable functions with , there is always a total and calculable function so that: ${\displaystyle r\colon \mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle r(n)\geq n}$ ${\displaystyle s\colon \mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle \operatorname {DTIME} (s)=\operatorname {DTIME} (r\circ s)}$

The above function cannot be time-constructed, otherwise this would be a contradiction to the hierarchy statements, which state that an increase in time or space for a calculation also results in an increase in the complexity class. ${\displaystyle s}$

example

There are computable functions s for which the following applies:

${\displaystyle \operatorname {DTIME} (s)=\operatorname {NSPACE} (s)=\operatorname {DTIME} (2^{O(s)})=\operatorname {NSPACE} (2^{2^{2^{s}}})=\operatorname {DTIME} (2^{2^{2^{2^{s}}}})}$

by applying the gap theorem with . ${\displaystyle r(n)=2^{2^{2^{2^{n}}}}}$

literature

• Allan Borodin: Computational Complexity and the Existence of Complexity Gaps . J. ACM 19 (1): 158-174 (1972)