Union-Theorem

Das Union-Theorem ist ein Ergebnis aus der Frühzeit der Forschung zur Komplexitätstheorie. Es geht auf eine Veröffentlichung von Ed McCreight und Albert Meyer aus dem Jahr 1969 zurück und sagt Folgendes aus: Ist eine Liste von Zeitschranken $t_{1},t_{2},\dots$ mit $t_{i+1}\geq t_{i}$ für alle i gegeben, so existiert eine Zeitschranke t, so dass ein Problem genau dann in Zeit t berechenbar ist, wenn es für irgendein $t_{i}$ berechenbar ist. Das Theorem lässt sich insbesondere zur Bildung von Komplexitätsklassen einsetzen und bildet damit eine der Grundlagen zur Formulierung der Hierarchiesätze. Beispielsweise folgt aus dem Theorem, dass Funktionen, die deterministisch in Polynomialzeit berechenbar sind, eine Komplexitätsklasse bilden.

In Kap. 12.6 der ersten Ausgabe von 1979 des Lehrbuchs von Hopcroft und Ullman finden sich Varianten des Union-Theorems. In neueren Auflagen fehlt dieses Kapitel.