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.