A Note on Randomized Polynomial Time

DOI10.1137/0216056MaRDI QIDQ3773343zbMATH OpenOpenAlexFDO

Authors Stuart A. Kurtz

Publication date 1987

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0216056

zbMATH Keywords

BPPrandom oraclesrandom polynomial time

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Cited in

(12)

• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• On independent random oracles
• Hardness vs randomness
• A zero-one law for RP and derandomization of AM if NP is not small
• The randomized complexity of initial value problems
• A note on deterministic and nondeterministic time complexity
• RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
• scientific article; zbMATH DE number 176508 (Why is no real title available?)
• Genericity, Randomness, and Polynomial-Time Approximations
• Towards a polynomial-time randomized algorithm for closed product-form networks
• Random CNF's are hard for the polynomial calculus
• Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?

This page was built for publication: A Note on Randomized Polynomial Time

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