A refinement of the McCreight-Meyer union theorem

Abstract

Abstract Using properties of Blum complexity measures and certain complexity class operators, we exhibit a total computable and non-decreasing function $$t_\textsf{poly}$$ t poly such that for all k , $$\Sigma _k\textsf{P}= \Sigma _k\textsf{TIME}(t_\textsf{poly})$$ Σ k P = Σ k TIME ( t poly ) , $$\textsf{BPP}= \textsf{BPTIME}(t_\textsf{poly})$$ BPP = BPTIME ( t poly ) , $$\textsf{RP}= \textsf{RTIME}(t_\textsf{poly})$$ RP = RTIME ( t poly ) , $$\textsf{UP}= \textsf{UTIME}(t_\textsf{poly})$$ UP = UTIME ( t poly ) , $$\textsf{PP}= \textsf{PTIME}(t_\textsf{poly})$$ PP = PTIME ( t poly ) , $$\textsf{Mod}_k\textsf{P}= \textsf{Mod}_k\textsf{TIME}(t_\textsf{poly})$$ Mod k P = Mod k TIME ( t poly ) , $$\textsf{PSPACE}= \textsf{DSPACE}(t_\textsf{poly})$$ PSPACE = DSPACE ( t 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.