Union theorem

The union theorem is a result from the 60s in computational complexity theory. It was published 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. 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 $t_{1},t_{2},\dots$ where $t_{i+1}\geq t_{i}$ for $i\in \mathbb {N} _{>0}$, there exists a time bound function $t$ such that a problem is computable in time bounded by $t$ if and only if there exists an $i$ such that the problem is computable in time bounded by $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 hirarchies in complexity theory.