A Refinement of the McCreight-Meyer Union Theorem
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910484864696320 |
|---|---|
| author | Fox, Matthew Karamchedu, Chaitanya |
| author_facet | Fox, Matthew Karamchedu, Chaitanya |
| contents | 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$, $Σ_k\mathsf{P} = Σ_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_08600 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Refinement of the McCreight-Meyer Union Theorem Fox, Matthew Karamchedu, Chaitanya Computational Complexity 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$, $Σ_k\mathsf{P} = Σ_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. |
| title | A Refinement of the McCreight-Meyer Union Theorem |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2406.08600 |