On relativized exponential and probabilistic complexity classes

DOI10.1016/S0019-9958(86)80012-2zbMath0628.68047OpenAlexW2082775279WikidataQ56039187 ScholiaQ56039187MaRDI QIDQ3765250

Hans Heller

Publication date: 1986

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80012-2

zbMATH Keywords

polynomial timesparse setsoracleprobabilistic complexityrelativized complexity classes

Mathematics Subject Classification ID

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

Related Items (23)

Hausdorff dimension and oracle constructions ⋮ Genericity and measure for exponential time ⋮ Geometric sets of low information content ⋮ An application of the translational method ⋮ \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ Probabilistic quantifiers and games ⋮ P-RAM vs. RP-RAM ⋮ Limitations of the upward separation technique ⋮ The power of natural properties as oracles ⋮ \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP] ⋮ An explicit separation of relativised random polynomial time and relativised deterministic polynomial time ⋮ Hard sets are hard to find ⋮ On the cutting edge of relativization: The resource bounded injury method ⋮ Separating complexity classes with tally oracles ⋮ If NP has polynomial-size circuits, then MA=AM ⋮ New collapse consequences of NP having small circuits ⋮ Non-deterministic exponential time has two-prover interactive protocols ⋮ Reductions to sets of low information content ⋮ Unnamed Item ⋮ AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly ⋮ Relativizing relativized computations ⋮ Genericity and measure for exponential time ⋮ \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs

This page was built for publication: On relativized exponential and probabilistic complexity classes