A Note on Randomized Polynomial Time

DOI10.1137/0216056zbMath0634.68041OpenAlexW2059312796MaRDI QIDQ3773343

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

random oraclesBPPrandom polynomial time

Mathematics Subject Classification ID

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

Related Items (4)

Hardness vs randomness ⋮ Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes ⋮ Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? ⋮ On independent random oracles

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