Publication:4723714
From MaRDI portal
zbMath0615.03024MaRDI QIDQ4723714
Publication date: 1986
Turing reducibility; polynomial reducibilities; random oracle; BPP; P; relativized complexity class; many-one-reducibility; pm-reducibility; probabilistic polynomial time bounded Turing machines; random relativization
03D15: Complexity of computation (including implicit computational complexity)
03D30: Other degrees and reducibilities in computability and recursion theory
03D10: Turing machines and related notions
Related Items
On the robustness of ALMOST-$\mathcal {R}$, Genericity and measure for exponential time, On complexity classes and algorithmically random languages, If not empty, NP-P is topologically large, Does truth-table of linear norm reduce the one-query tautologies to a random oracle?, Dimension extractors and optimal decompression, An improved zero-one law for algorithmically random sequences, On independent random oracles, Circuit size relative to pseudorandom oracles, On collapsing the polynomial-time hierarchy, Genericity and measure for exponential time, Weak completeness notions for exponential time, Bounded truth table does not reduce the one-query tautologies to a random oracle, Polynomial-time reducibilities and ``almost all oracle sets