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.

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

Formal: Für totale, berechenbare Funktionen r mit $r(n) \geq n \forall n$, gibt es immer eine totale und berechenbare Funktion $s: \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)