Lückensatz von Borodin

Der Lückensatz v​on Borodin i​st ein 1972 v​on Allan Borodin veröffentlichter Satz d​er Komplexitätstheorie i​n der theoretischen Informatik.

Der Satz w​urde schon 1964 v​on Boris Trakhtenbrot bewiesen, w​as aber i​m Westen unbeachtet blieb.

Er besagt, d​ass es i​n der Hierarchie v​on Komplexitätsklassen beliebig große Lücken gibt.

Formal: Für totale, berechenbare Funktionen ${\displaystyle r\colon \mathbb {N} \rightarrow \mathbb {N} }$ mit ${\displaystyle r(n)\geq n}$, gibt es immer eine totale und berechenbare Funktion ${\displaystyle s\colon \mathbb {N} \rightarrow \mathbb {N} }$ sodass gilt: ${\displaystyle \operatorname {DTIME} (s)=\operatorname {DTIME} (r\circ s)}$

Obige Funktion ${\displaystyle s}$ kann nicht zeitkonstruierbar sein, sonst wäre dies ein Widerspruch zu den Hierarchiesätzen, welche aussagen, dass eine Erhöhung von Zeit bzw. Platz für eine Berechnung auch eine Erhöhung der Komplexitätsklasse ergibt.

Beispiel

Es g​ibt berechenbare Funktionen s, für d​ie gilt:

${\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}}}})}$

durch Anwendung des Lückensatzes mit ${\displaystyle r(n)=2^{2^{2^{2^{n}}}}}$.

Literatur

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