Pages that link to "Item:Q3765250"

The following pages link to On relativized exponential and probabilistic complexity classes (Q3765250):

Displaying 23 items.

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