Relativizing relativized computations

DOI10.1016/0304-3975(89)90164-3MaRDI QIDQ1822968zbMATH OpenOpenAlexFDO

Authors Stephen R. Mahaney, Neil Immerman

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

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

Recommendations

• scientific article; zbMATH DE number 4099277
• scientific article; zbMATH DE number 4011940
• Relativized circuit complexity
• scientific article; zbMATH DE number 500314
• Positive relativizations of the \(P=?\) NP problem

Cites work

• A second step toward the polynomial hierarchy
• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3594673 (Why is no real title available?)
• On Isomorphisms and Density of NP and Other Complete Sets
• On relativized exponential and probabilistic complexity classes
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Relativized circuit complexity
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy

Cited in

(20)

• Relativized circuit complexity
• Separating complexity classes with tally oracles
• Easy sets and hard certificate schemes
• Relativized worlds with an infinite hierarchy
• Competing provers yield improved Karp-Lipton collapse results
• Further oracles separating conjectures about incompleteness in the finite domain
• An oracle separating conjectures about incompleteness in the finite domain
• Relating Computational Effects by ⊤ ⊤-Lifting
• Relational Parametricity for Computational Effects
• Sparse Sets in : Relativizations
• scientific article; zbMATH DE number 4099277 (Why is no real title available?)
• scientific article; zbMATH DE number 1775405 (Why is no real title available?)
• scientific article; zbMATH DE number 2163013 (Why is no real title available?)
• Monotonous and randomized reductions to sparse sets
• scientific article; zbMATH DE number 866668 (Why is no real title available?)
• Reductions to sets of low information content (extended abstract)
• Relativized isomorphisms of NP-complete sets
• General relativistic hypercomputing and foundation of mathematics
• Oracle-dependent properties of the lattice of NP sets
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP

This page was built for publication: Relativizing relativized computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1822968)