We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Borel complexity and Ramsey largeness of sets of oracles separating complexity classes.
- Authors
Creiner, Alex; Jackson, Stephen
- Abstract
We prove two sets of results concerning computational complexity classes. First, we propose a new variation of the random oracle hypothesis, originally posed by Bennett and Gill after they showed that relative to a randomly chosen oracle, P≠NP$\mathbf {P}\ne \mathbf {NP}$ with probability 1. Their original hypothesis was quickly disproven in several ways, most famously in 1992 with the result that IP=PSPACE$\mathbf {IP} = \mathbf {PSPACE}$, in spite of the classes being shown unequal with probability 1. Here we propose a variation of what it means to be "large" using the Ellentuck topology. In this new context, we demonstrate that the set of oracles separating NP$\mathbf {NP}$ and co-NP$\mathbf {co}\text{-}\mathbf {NP}$ is not small, and obtain similar results for the separation of PSPACE$\mathbf {PSPACE}$ from PH$\mathbf {PH}$ along with the separation of NP$\mathbf {NP}$ from BQP$\mathbf {BQP}$. We also show that the set of oracles equatingIP$\mathbf {IP}$ with PSPACE$\mathbf {PSPACE}$ is large in this new sense. We demonstrate that this version of the hypothesis provides a sufficient condition for unrelativized relationships, at least in the cases considered here. Second, we examine the descriptive complexity of the classes of oracles providing the separations for these various classes, and determine their exact placement in the Borel hierarchy.
- Subjects
RAMSEY theory; COMPUTATIONAL complexity; RAMSEY numbers; TOPOLOGY
- Publication
Mathematical Logic Quarterly, 2023, Vol 69, Issue 3, p267
- ISSN
0942-5616
- Publication type
Article
- DOI
10.1002/malq.202200068