Lückensatz von Borodin

Der Lückensatz von Borodin ist ein 1972 von Allan Borodin veröffentlichter Satz der Komplexitätstheorie in der theoretischen Informatik.

Der Satz wurde schon 1964 von Boris Trakhtenbrot bewiesen, was aber im Westen unbeachtet blieb.

Er besagt, dass es in der Hierarchie von Komplexitätsklassen beliebig große Lücken gibt.

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

Obige Funktion $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 gibt berechenbare Funktionen s, für die gilt:

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