A Refinement of the McCreight-Meyer Union Theorem

Abstract

Using properties of Blum complexity measures and certain complexity class operators, we exhibit a total computable and non-decreasing function $t_{\mathsf{poly}}$ such that for all $k$, $\hat{I}{\pounds }_k\mathsf{P}=\hat{I}{\pounds }_k\mathsf{TIME}(t_{\mathsf{poly}})$, $\mathsf{BPP}=\mathsf{BPTIME}(t_{\mathsf{poly}})$, $\mathsf{RP}=\mathsf{RTIME}(t_{\mathsf{poly}})$, $\mathsf{UP}=\mathsf{UTIME}(t_{\mathsf{poly}})$, $\mathsf{PP}=\mathsf{PTIME}(t_{\mathsf{poly}})$, ${\mathsf{Mod}}_k\mathsf{P}={\mathsf{Mod}}_k\mathsf{TIME}(t_{\mathsf{poly}})$, $\mathsf{PSPACE}=\mathsf{DSPACE}(t_{\mathsf{poly}})$, and so forth. A similar statement holds for any collection of language classes, provided that each class is definable by applying a certain complexity class operator to some Blum complexity class.

11 pages