This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles. (February 2023)

The union theorem is a result from the 60s in computational complexity theory. It was published^[1] in 1969 by Ed McCreight and Albert Meyer.

Originally it is stated for general Blum complexity classes, but it is most relevant for DTIME, NTIME, DSPACE or NSPACE as stated in ch. 12.6 of first edition from 1979 of the textbook of Hopcroft and Ullman.^[2] This chapter was removed from newer editions, however.

The theorem for time complexity roughly states the following. Given a list of monotonically increasing time bound functions ${\displaystyle t_{1},t_{2},\dots }$ where ${\displaystyle t_{i+1}\geq t_{i}}$ for ${\displaystyle i\in \mathbb {N} _{>0}}$, there exists a time bound function ${\displaystyle t}$ such that a problem is computable in time bounded by ${\displaystyle t}$ if and only if there exists an ${\displaystyle i}$ such that the problem is computable in time bounded by ${\displaystyle t_{i}}$.

The theorem can be applied to show that complexity classes like P are well-defined. Together with the speedup theorem, the gap theorem and the time and space hierarchy theorems it is a basis for hierarchies in complexity theory.