2025/02/13 by Thekla Hamm, Lucas Meijer, Hamm, Thekla +5
Computer Science · #68Q15 #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #Web Application Security Vulnerabilities
paper · pdf · doi:10.48550/arxiv.2502.09279
openalex publication_date 2025/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ⊆ ER ⊆ PSPACE and furthermore PH ⊆ RPH ⊆ 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: - RPHO proper subset of PSPACEO, - Σk+1O not contained in ΣkRO, for all k≥ 0, - ΣkRO proper subset of Σk+1RO, for all k≥ 0, - BQPO not contained in RPHO. 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.