Relativizations of Unambiguous and Random Polynomial Time Classes

DOI10.1137/0215035MaRDI QIDQ3750121zbMATH OpenOpenAlexFDO

Authors John G. Geske, Joachim Grollmann

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

immunitypublic-key cryptosystemsrandom computationsrecursive oraclerelativized complexity classesTuring machinesunique solutions

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) Cryptography (94A60)

Recommendations

• scientific article; zbMATH DE number 4011940
• Restricted relativizations of probabilistic polynomial time
• An explicit separation of relativised random polynomial time and relativised deterministic polynomial time
• scientific article; zbMATH DE number 3885883
• scientific article; zbMATH DE number 3995648
• Refining Nondeterminism in Relativizations of Complexity Classes
• scientific article; zbMATH DE number 4106269
• On relativized exponential and probabilistic complexity classes
• scientific article; zbMATH DE number 227415
• Relativized generic classes P and NP

Cited in

(7)

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

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

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