Le 12-avr.-05, à 05:26, Stathis Papaioannou a écrit :
> And does it really make much difference, whether we are talking truly
> random or intractably pseudo-random?
You may be interested to know that the class
of problems soluble by machine with
pseudo-random oracle is properly contained
in the class of problems soluble by machine with
(genuine) random oracle:
KURTZ S. A., 1983, On the Random Oracle Hypothesis, Information and
Control, 57, pp. 40-47.
Bruno
http://iridia.ulb.ac.be/~marchal/
Received on Tue Apr 12 2005 - 03:28:42 PDT