From: Christian Szegedy (szegedy@or.uni-bonn.de)
Date: Thu Dec 04 2003 - 04:23:04 MST
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
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:43 MDT