**From:** Christian Szegedy (*szegedy@or.uni-bonn.de*)

**Date:** Thu Dec 04 2003 - 04:23:04 MST

**Next message:**Brian Atkins: "Re: the virtues of noise"**Previous message:**Perry E.Metzger: "Re: the virtues of noise"**In reply to:**Eugen Leitl: "Re: Edge.org: Jaron Lanier"**Next in thread:**Mitchell Porter: "Re: Edge.org: Jaron Lanier"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Eugen Leitl wrote:

*>>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.
*

*>>
*

*>>
*

*>
*

*>Very good. Does this hypothesis come with a recipe how to use
*

*>that to find a recipe for the entire class of problems? It would
*

*>be quite sterile otherwise.
*

*>
*

There are a lot of special cases supporting this conjecture. There

are even quite general principles and derandomization techniques

commonly used in the theory of algorithms. Besides, no (NP \cap RP)

problem turned out to be NP complete yet.

There is one vague, intuitive hint which would plausibily support

this hypothesis: normally if one uses random bits, you don't

need that they are completely random in every possible respect,

just that they are independent enough from some "variables"

occuring in the problem. So normally, you can always find a

sufficiently random pseudo-random generator which does the

trick for a concrete problem. Nevertheless, proving the polynomiality

after finding a nice pseudo-random source is often a very

hard theoretical task. Several special cases of the general

hypothesis have become long-standing conjectures.

And I would warn you, you should not underestimate the practical

relevance of this theoretical stuff. E.g. polynomial computability

is a quite an ad-hoc definition, still it covers quite well the

practically tractable problems. Of course, there are mismatches,

but the overall (admittedly surprising) practical relevance of the

concept is experimentally well established.

Best Regards, Christian

**Next message:**Brian Atkins: "Re: the virtues of noise"**Previous message:**Perry E.Metzger: "Re: the virtues of noise"**In reply to:**Eugen Leitl: "Re: Edge.org: Jaron Lanier"**Next in thread:**Mitchell Porter: "Re: Edge.org: Jaron Lanier"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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