Relativizations of Unambiguous and Random Polynomial Time Classes

DOI10.1137/0215035zbMath0609.68038OpenAlexW2042291172MaRDI QIDQ3750121

Joachim Grollmann, John G. Geske

Publication date: 1986

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

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

zbMATH Keywords

Turing machinesimmunityunique solutionspublic-key cryptosystemsrecursive oraclerelativized complexity classesrandom computations

Mathematics Subject Classification ID

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

Related Items (6)

Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ The isomorphism conjecture holds and one-way functions exist relative to an oracle ⋮ Immunity and simplicity in relativizations of probabilistic complexity classes ⋮ Strong self-reducibility precludes strong immunity ⋮ Oracles for structural properties: The isomorphism problem and public-key cryptography ⋮ Qualitative relativizations of complexity classes

This page was built for publication: Relativizations of Unambiguous and Random Polynomial Time Classes