Relativized Questions Involving Probabilistic Algorithms
From MaRDI portal
Publication:3935473
DOI10.1145/322290.322306zbMath0477.68037OpenAlexW2078999165WikidataQ128587515 ScholiaQ128587515MaRDI QIDQ3935473
Publication date: 1982
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322290.322306
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (27)
A complexity theory for feasible closure properties ⋮ On randomized versus deterministic computation ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ NP is as easy as detecting unique solutions ⋮ A general method to construct oracles realizing given relationships between complexity classes ⋮ One-way functions and the nonisomorphism of NP-complete sets ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ The isomorphism conjecture holds and one-way functions exist relative to an oracle ⋮ On randomized versus deterministic computation ⋮ Relativized alternation and space-bounded computation ⋮ Probabilistic quantifiers and games ⋮ Mathematical problems in cryptology ⋮ A tight relationship between generic oracles and type-2 complexity theory ⋮ A map of witness maps: new definitions and connections ⋮ Classifying the computational complexity of problems ⋮ Robust machines accept easy sets ⋮ Immunity and simplicity in relativizations of probabilistic complexity classes ⋮ On sets polynomially enumerable by iteration ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Separating complexity classes with tally oracles ⋮ Immunity, simplicity, probabilistic complexity classes and relativizations ⋮ Helping by unambiguous computation and probabilistic computation ⋮ Oracles for structural properties: The isomorphism problem and public-key cryptography ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ Qualitative relativizations of complexity classes ⋮ On some natural complete operators ⋮ Relativized circuit complexity
This page was built for publication: Relativized Questions Involving Probabilistic Algorithms
