Back to search

University of North Texas

On the Descriptive Complexity and Ramsey Measure of Sets of Oracles Separating Common Complexity Classes

Abstract

dc:description

As soon as Bennett and Gill first demonstrated that, relative to a randomly chosen oracle, P is not equal to NP with probability 1, the random oracle hypothesis began piquing the interest of mathematicians and computer scientists. This was quickly disproven in several ways, most famously in 1992 with the result that IP equals PSPACE, in spite of the classes being shown unequal with probability 1. Here, we propose what could be considered strengthening of the random oracle hypothesis, using a stricter notion of what it means for a set to be 'large'. In particular, we suggest using largeness with respect to the Ramsey forcing notion. In this new context, we demonstrate that the set of oracles separating NP and coNP is 'not small', and obtain similar results for the separation of PSPACE from PH along with the separation of NP from BQP. In a related set of results, we demonstrate that these classes are all of the same descriptive complexity. Finally we demonstrate that this strengthening of the hypothesis turns it into a sufficient condition for unrelativized relationships, at least in the three cases considered here.

Degree

thesis:*
Grantor dc:publisher
University of North Texas
Year dc:date
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Creiner, Alex
Contributors dc:contributor
  • Jackson, Stephen
  • Iaia, Joseph
  • Song, Kai-Sheng

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Public
  • Creiner, Alex
  • Copyright
  • Copyright is held by the author, unless otherwise noted. All rights Reserved.
Language dc:language
English

Identifiers

dc:identifier.*
Identifier
local-cont-no: submission_3097
https://digital.library.unt.edu/ark:/67531/metadc1987243/
ark: ark:/67531/metadc1987243

Chain of custody

source
Harvested from
University of North Texas
Base URL
digital.library.unt.edu/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Creiner, Alex. On the Descriptive Complexity and Ramsey Measure of Sets of Oracles Separating Common Complexity Classes. University of North Texas, 2022. https://doi.org/10.12794/metadc1987243