Relativizing relativized computations

DOI10.1016/0304-3975(89)90164-3zbMath0679.68084OpenAlexW1969813680MaRDI QIDQ1822968

Stephen R. Mahaney

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90164-3

zbMATH Keywords

models of computationoraclesrelativized computations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (5)

\(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP] ⋮ Separating complexity classes with tally oracles ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Reductions to sets of low information content ⋮ Monotonous and randomized reductions to sparse sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relativized circuit complexity
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• On relativized exponential and probabilistic complexity classes
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets

This page was built for publication: Relativizing relativized computations