Re: Edge.org: Jaron Lanier

From: Christian Szegedy (szegedy@or.uni-bonn.de)
Date: Wed Dec 03 2003 - 09:12:04 MST


Eliezer S. Yudkowsky wrote:

> Call me a Shannon-worshipper, but I just don't see how you can do more
> computation with half a bit than a whole bit.

I would second to that. However the problem is mathmatically intriguing.
For example there is the hypothesis that NP \cap RP = P. That is
anything polynomially checkable and polynomially solvable using
random bits can also be computed polynomially *without* using
random bits.

Nevetherless this is only a conjecture. Nobody could disprove it yet,
and a lot of complexity theoretists think, it's true.

Best Regards, Christian



This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:43 MDT