Misplaced Pages

This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (February 2023)

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 ${\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.

References

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

• Computational complexity theory