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^[1] und sagt Folgendes aus: Ist eine Liste von Zeitschranken ${\displaystyle t_{1},t_{2},\dots }$ mit ${\displaystyle 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 ${\displaystyle 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^[2] finden sich Varianten des Union-Theorems. In neueren Auflagen fehlt dieses Kapitel.

1. ↑ E. M. McCreight, A. R. Meyer: Classes of Computable Functions Defined by Bounds on Computation: Preliminary Report. ACM Symposium on Theory of Computing. In: Proceedings of the First Annual ACM Symposium on Theory of Computing. STOC '69. Association for Computing Machinery, New York, NY, USA, Marina del Rey, California, USA 1969, ISBN 978-1-4503-7478-1, S. 79–88, doi:10.1145/800169.805423 (englisch). 
2. ↑ John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. 1. Auflage. Addison-Wesley, 1979, ISBN 0-201-02988-X (englisch, archive.org).