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