A Refinement of the McCreight-Meyer Union Theorem
<|reference_start|>A Refinement of the McCreight-Meyer Union Theorem: 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$, $\Sigma_k\mathsf{P} = \Sigma_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.<|reference_end|>
@article{fox2024a,
    title={A Refinement of the McCreight-Meyer Union Theorem},
    author={Matthew Fox and Chaitanya Karamchedu},
    journal={arXiv preprint arXiv:2406.08600},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.08600},
    primaryClass={cs.CC}
}