Relativizations of unambiguous and random polynomial time classes. (English) Zbl 0609.68038

We study relationships between P, NP, and the unambiguous and random time classes, U and R. Questions concerning these relationships are motivated by complexity issues in public-key cryptosystems. We prove that there exists a recursive oracle A such that \(P^ A\neq U^ A\neq NP^ A\), and such that the first inequality is ”strong”, i.e., there exists a \(P^ A\)-immune set in \(U^ A\). Further, we construct a recursive oracle B such that \(U^ B\) contains an \(R^ B\)-immune set. As a corollary, we obtain \(P^ B\neq R^ B\neq NP^ B\) and both inequalities are strong. By use of the techniques employed in the proof that \(P^ A\neq U^ A\neq NP^ A\), we are also able to solve an open problem raised by R. V. Book, T. J. Long and A. L. Selman [ibid. 13, 461-487 (1984; Zbl 0599.03041)].


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


Zbl 0599.03041
Full Text: DOI