Relativized Questions Involving Probabilistic Algorithms

DOI10.1145/322290.322306zbMath0477.68037OpenAlexW2078999165WikidataQ128587515 ScholiaQ128587515MaRDI QIDQ3935473

Charles W. Rackoff

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

zbMATH Keywords

probabilistic computationrelativized computation, oracle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

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