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/