Oracles for structural properties: The isomorphism problem and public-key cryptography (Q1190988)

Relativized computations are known to be a useful tool for assessing the difficulty of answering some important open questions in structural complexity theory. The main result of the paper is a construction of an oracle relative to which -- besides other properties -- all sets complete in the second level of polynomial hierarchy are p-isomorphic, and there do not exist public-key cryptosystems that are NP-hard to crack. Some related results are proved as well, and all together provide a better insight into the area developed from the Berman - Hartmanis isomorphism conjecture, and into the cryptographic complexity investigating theoretical questions of the existence of public-key cryptosystems.