Oracle Separations for RPH
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909829402984448 |
|---|---|
| author | Hamm, Thekla Meijer, Lucas Miltzow, Tillmann Patro, Subhasree |
| author_facet | Hamm, Thekla Meijer, Lucas Miltzow, Tillmann Patro, Subhasree |
| contents | While theoretical computer science primarily works with discrete models of computation, like the Turing machine and the wordRAM, there are many scenarios in which introducing real computation models is more adequate. We want to compare real models of computation with discrete models of computation. We do this by means of oracle separation results.
We define the notion of a real Turing machine as an extension of the (binary) Turing machine by adding a real tape. Using those machines, we define and study the real polynomial hierarchy RPH. We are interested in RPH as the first level of the hierarchy corresponds to the well-known complexity class ER. It is known that $NP \subseteq ER \subseteq PSPACE$ and furthermore $PH \subseteq RPH \subseteq PSPACE$. We are interested to know if any of those inclusions are tight. In the absence of unconditional separations of complexity classes, we turn to oracle separation. We develop a technique that allows us to transform oracle separation results from the binary world to the real world. As applications, we show there are oracles such that:
- $RPH^O$ proper subset of $PSPACE^O$,
- $Σ_{k+1}^O$ not contained in $Σ_kR^O$, for all $k\geq 0$,
- $Σ_kR^O$ proper subset of $Σ_{k+1}R^O$, for all $k\geq 0$,
- $BQP^O$ not contained in $RPH^O$.
Our results hint that ER is strictly contained in PSPACE and that there is a separation between the different levels of the real polynomial hierarchy. We also bound the power of real computations by showing that NP-hard problems are unlikely to be solvable using polynomial time on a realRAM. Furthermore, our oracle separations hint that polynomial-time quantum computing cannot be simulated on an efficient real Turing machine. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09279 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Oracle Separations for RPH Hamm, Thekla Meijer, Lucas Miltzow, Tillmann Patro, Subhasree Computational Complexity 68Q15 F.1.3 While theoretical computer science primarily works with discrete models of computation, like the Turing machine and the wordRAM, there are many scenarios in which introducing real computation models is more adequate. We want to compare real models of computation with discrete models of computation. We do this by means of oracle separation results. We define the notion of a real Turing machine as an extension of the (binary) Turing machine by adding a real tape. Using those machines, we define and study the real polynomial hierarchy RPH. We are interested in RPH as the first level of the hierarchy corresponds to the well-known complexity class ER. It is known that $NP \subseteq ER \subseteq PSPACE$ and furthermore $PH \subseteq RPH \subseteq PSPACE$. We are interested to know if any of those inclusions are tight. In the absence of unconditional separations of complexity classes, we turn to oracle separation. We develop a technique that allows us to transform oracle separation results from the binary world to the real world. As applications, we show there are oracles such that: - $RPH^O$ proper subset of $PSPACE^O$, - $Σ_{k+1}^O$ not contained in $Σ_kR^O$, for all $k\geq 0$, - $Σ_kR^O$ proper subset of $Σ_{k+1}R^O$, for all $k\geq 0$, - $BQP^O$ not contained in $RPH^O$. Our results hint that ER is strictly contained in PSPACE and that there is a separation between the different levels of the real polynomial hierarchy. We also bound the power of real computations by showing that NP-hard problems are unlikely to be solvable using polynomial time on a realRAM. Furthermore, our oracle separations hint that polynomial-time quantum computing cannot be simulated on an efficient real Turing machine. |
| title | Oracle Separations for RPH |
| topic | Computational Complexity 68Q15 F.1.3 |
| url | https://arxiv.org/abs/2502.09279 |