Borel complexity and Ramsey largeness of sets of oracles separating complexity classes

DOI10.1002/MALQ.202200068arXiv2210.12289MaRDI QIDQ6096803

No author found.

Publication date: 15 September 2023

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2210.12289

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Cites Work

• Unnamed Item
• Random oracles separate PSPACE from the polynomial-time hierarchy
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• The random oracle hypothesis is false
• Parity, circuits, and the polynomial-time hierarchy
• On the random oracle hypothesis
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• IP = PSPACE
• Quantum Complexity Theory
• Strengths and Weaknesses of Quantum Computing

This page was built for publication: Borel complexity and Ramsey largeness of sets of oracles separating complexity classes