English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove two sets of results concerning computational complexity classes. Thefirst concerns a variation of the random oracle hypothesis posed by Bennett andGill after they showed that relative to a randomly chosen oracle, P not equalNP with probability 1. This hypothesis was quickly disproven in several ways,most famously in 1992 with the result that IP equals PSPACE, in spite of theclasses being shown unequal with probability 1. Here we propose a variation ofwhat it means to be ``large'' using the Ellentuck topology. In this newcontext, we demonstrate that the set of oracles separating NP and co-NP is notsmall, and obtain similar results for the separation of PSPACE from PH alongwith the separation of NP from BQP. We demonstrate that this version of thehypothesis turns it into a sufficient condition for unrelativizedrelationships, at least in the three cases considered here. Second, we examplethe descriptive complexity of the classes of oracles providing the separationsfor these various classes, and determine their exact placement in the Borelhierarchy.

Complexity and Ramsey Largeness of Sets of Oracles Separating Complexity Classes