scientific article; zbMATH DE number 3995648

Publication date: 1986

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Turing reducibility polynomial reducibilities random oracle BPP P relativized complexity class many-one-reducibility pm-reducibility probabilistic polynomial time bounded Turing machines random relativization

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10)

Related Items (14)

On collapsing the polynomial-time hierarchy ⋮ Genericity and measure for exponential time ⋮ Polynomial-time reducibilities and ``almost all oracle sets ⋮ Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ An improved zero-one law for algorithmically random sequences ⋮ On complexity classes and algorithmically random languages ⋮ On independent random oracles ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ If not empty, NP-P is topologically large ⋮ Circuit size relative to pseudorandom oracles ⋮ Dimension extractors and optimal decompression ⋮ On the robustness of ALMOST-$\mathcal {R}$ ⋮ Genericity and measure for exponential time ⋮ Weak completeness notions for exponential time

This page was built for publication: