On Mon, Aug 28, 2006 at 03:41:00PM +0200, Bruno Marchal wrote:
> 
> 
> Le 27-août-06, à 12:43, Russell Standish a écrit :
> 
> 
> 
> > I recall reading this paper, and the followup entitled "The Random
> > Oracle Hypothesis is False" by Chang et al.
> 
> 
> Have you the reference? Do you know if Chang has found a math error, or 
> a conceptual mishandling? I would be interested to know.
> 
> 

The ref is


@Article{Chang-etal94,
  author =       {Richard Chang and Benny Chor and Oded Goldreich and Juris 
Hartmanis and Johan H\aa{}stad and Desh Ranjan and Pankaj Rohatgi},
  title =        {The Random Oracle Hypothesis is False},
  journal =      {Journal of Computer and System Sciences},
  year =         1994,
  volume =       49,
  pages =        {24-39}
}

Google it - its on the web.

> 
> 
> >> From recollection though, the claim was of superior algorithmic
> > performance (ie solving NP problems in P time) rather than solving
> > uncomputable problems.
> 
> 
> 
> I doubt this very much, but I will check and let you know,
> 


There is also the classic Leeuw et al paper (1957) demonstrating that
probabilistic TMs are no more powerful than the regular thing.

Anyway, I appreciate you checking - such a claim as you're saying
would be very interesting.

> 
> Bruno
> 
> 
> http://iridia.ulb.ac.be/~marchal/
> 
> 
> 
-- 
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.

----------------------------------------------------------------------------
A/Prof Russell Standish                  Phone 8308 3119 (mobile)
Mathematics                                    0425 253119 (")
UNSW SYDNEY 2052                         [EMAIL PROTECTED]             
Australia                                http://parallel.hpc.unsw.edu.au/rks
            International prefix  +612, Interstate prefix 02
----------------------------------------------------------------------------


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---

Reply via email to