Union theorem
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 [math]\displaystyle{ t_1,t_2,\dots }[/math] where [math]\displaystyle{ t_{i+1} \ge t_i }[/math] for [math]\displaystyle{ i \in \mathbb{N}_{\gt 0} }[/math], there exists a time bound function [math]\displaystyle{ t }[/math] such that a problem is computable in time bounded by [math]\displaystyle{ t }[/math] if and only if there exists an [math]\displaystyle{ i }[/math] such that the problem is computable in time bounded by [math]\displaystyle{ t_i }[/math].
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.
References
- ↑ McCreight, E. M.; Meyer, A. R. (1969). "Classes of Computable Functions Defined by Bounds on Computation: Preliminary Report" (in English). ACM Symposium on Theory of Computing. Marina del Rey, California, USA: Association for Computing Machinery, New York, NY, USA. pp. 79–88. doi:10.1145/800169.805423. ISBN 9781450374781. https://doi.org/10.1145/800169.805423.
- ↑ Hopcroft, John E.; Ullman, Jeffrey D. (1979) (in English). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-02988-X. https://archive.org/details/introductiontoau00hopc.
 |  |
