Separating complexity classes with tally oracles
From MaRDI portal
Publication:1185002
DOI10.1016/0304-3975(92)90318-AzbMath0745.68048OpenAlexW2032491581MaRDI QIDQ1185002
Roy S. Rubinstein, Hemaspaandra, Lane A.
Publication date: 28 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)90318-a
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- Robust machines accept easy sets
- Strong nondeterministic polynomial-time reducibilities
- Relativized circuit complexity
- Complexity classes without machines: on complete languages for UP
- Promise problems complete for complexity classes
- On sparse oracles separating feasible complexity classes
- A uniform approach to define complexity classes
- Relative complexity of checking and evaluating
- Sets with small generalized Kolmogorov complexity
- Relativizing relativized computations
- Complexity classes and sparse oracles
- One-way functions and the nonisomorphism of NP-complete sets
- The polynomial-time hierarchy and sparse oracles
- The complexity of promise problems with applications to public-key cryptography
- On relativized exponential and probabilistic complexity classes
- The Boolean Hierarchy II: Applications
- Relativized Questions Involving Probabilistic Algorithms
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Computational Complexity of Probabilistic Turing Machines
