scientific article; zbMATH DE number 3995648

MaRDI QIDQ4723714zbMATH OpenFDO

Authors Klaus Ambos-Spies

Publication date 1986

zbMATH Keywords

BPPmany-one-reducibilityPpm-reducibilitypolynomial reducibilitiesprobabilistic polynomial time bounded Turing machinesrandom oraclerandom relativizationrelativized complexity classTuring reducibility

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4049050
• On relativized probabilistic polynomial time algorithms
• Separations by random oracles and ``almost classes for generalized reducibilities
• A Pseudorandom Oracle Characterization of ${\text{BPP}}$
• An observation on probability versus randomness with applications to complexity classes

Cited in

(28)

• 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
• On relativized probabilistic polynomial time algorithms
• Strong Medvedev reducibilities and the KL-randomness problem
• Dimension characterizations of complexity classes
• 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
• A Pseudorandom Oracle Characterization of ${\text{BPP}}$
• scientific article; zbMATH DE number 3880118 (Why is no real title available?)
• Separations by random oracles and ``almost classes for generalized reducibilities
• Relativizations of Unambiguous and Random Polynomial Time Classes
• scientific article; zbMATH DE number 4049050 (Why is no real title available?)
• Genericity, Randomness, and Polynomial-Time Approximations
• An observation on probability versus randomness with applications to complexity classes
• On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
• scientific article; zbMATH DE number 2011858 (Why is no real title available?)
• On the robustness of ALMOST-$\mathcal {R}$
• On complexity classes and algorithmically random languages (extended abstract)
• Genericity and measure for exponential time (extended abstract)
• Random CNF's are hard for the polynomial calculus
• On completeness under random reductions
• If not empty, NP-P is topologically large
• Does truth-table of linear norm reduce the one-query tautologies to a random oracle?

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4723714)