On relativized exponential and probabilistic complexity classes
From MaRDI portal
Recommendations
Cited in
(43)- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
- Probabilistic quantifiers and games
- Separating complexity classes with tally oracles
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
- On the \(\delta \to 0\) limit in probabilistic complexity
- Genericity and measure for exponential time
- Geometric sets of low information content
- On relativized probabilistic polynomial time algorithms
- Relativizing relativized computations
- Hard sets are hard to find
- Exact complexity: the spectral decomposition of intrinsic computation
- Hausdorff dimension and oracle constructions
- P-RAM vs. RP-RAM
- Limitations of the upward separation technique
- Relativizations comparing NP and exponential time
- On Relativized Polynomial and Exponential Computations
- scientific article; zbMATH DE number 3926244 (Why is no real title available?)
- scientific article; zbMATH DE number 3958736 (Why is no real title available?)
- Relativizations of Unambiguous and Random Polynomial Time Classes
- scientific article; zbMATH DE number 4011940 (Why is no real title available?)
- scientific article; zbMATH DE number 4045155 (Why is no real title available?)
- scientific article; zbMATH DE number 4074484 (Why is no real title available?)
- On Tally Relativizations of $BP$-Complexity Classes
- An application of the translational method
- On randomized versus deterministic computation
- On the cutting edge of relativization: the resource bounded injury method
- New collapse consequences of NP having small circuits
- scientific article; zbMATH DE number 951900 (Why is no real title available?)
- On the Structure of Logspace Probabilistic Complexity Classes
- Genericity and measure for exponential time (extended abstract)
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- Reductions to sets of low information content (extended abstract)
- scientific article; zbMATH DE number 227415 (Why is no real title available?)
- The power of natural properties as oracles
- Circuit complexity before the dawn of the new millennium
- If NP has polynomial-size circuits, then MA=AM
- Non-deterministic exponential time has two-prover interactive protocols
- Symmetric exponential time requires near-maximum circuit size
- Relativized succinct arguments in the ROM do not exist
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- \(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
This page was built for publication: On relativized exponential and probabilistic complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3765250)
