<p>Any concrete derandomization result gives evidence that P=BPP. As such PRIMES in P (Agrawal-Kayal-Saxena'02) is one good example. Generally, there are few natural problems in BPP that are not known to be in P (Polynomial Identity Testing is one notable exception.)</p>

<p>Similar in spirit to the result you mention, Hastad-Impagliazzo-Levin-Luby '99 showed that the existence of one-way functions implies the existence of pseudorandom generators. While this does not directly imply P=BPP based on the existence of one-way functions, it does show that pseudorandom generators follow from minimal cryptographic assumptions. This may be seen as another hint that BPP is not more powerful than P.</p>

CC BY-SA 2.5
2010-08-16T23:43:38.783Z
2010-08-16T23:43:38.783Z
Moritz
<p>It's important to note that saying "probabilistic reductions can [probably] be derandomized" is much stronger than P=RP.  In fact, one formalization of the notion of derandomizing all randomized reductions is that $P^X=RP^X$ <em>relative to every oracle $X$</em>, which we know is false (e.g. Heller. Relativized polynomial hierarchies extending two levels, Mathematical Systems Theory 17(2):71-84, 1984 gives an oracle where $ZPP=RP=EXP$ which is not equal to $P$ by the Time Hierarchy Theorem).</p>

<p>The above is, of course, talking about derandomizing randomized polynomial-time Turing reductions, rather than the usual polynomial-time many-one reductions.  I wouldn't be surprised if Heller's oracle can be adapted to give a set X such that for all Y, Y is exponential-time many-one reducible to X iff Y is RP-reducible to X, but without going through the construction I couldn't swear to it.</p>

CC BY-SA 2.5
2010-08-17T04:24:34.323Z
2010-08-21T00:58:48.257Z
2010-08-21T00:58:48.257Z
Joshua Grochow
<p><a href="http://dx.doi.org/10.1016/0304-3975%2886%2990135-0" rel="nofollow">Valiant and Vazirani showed in 1986</a> that there is a randomized reduction of SAT to $USAT_Q$, which is the decision problem based on SAT where only the difference between satisfiable and unsatisfiable instances matters.  If $Q = \bot$ is the false predicate, then $USAT_{\bot}$ is the problem of deciding whether there is precisely one solution.</p>

<p>A solution to a Boolean formula $\phi$ is a (0,1)-vector assigning truth values to the free variables in $\phi$, so that $\phi$ is satisfied.  A $k$-isolated solution $x$ to $\phi$ is a solution, with the additional property that any other solution differs in more than $k$ values.  (Alternately, $x$ is a $k$-isolated solution if the Hamming distance of $x$ to any other solution exceeds $k$.)</p>

<p>Let <a href="http://constraints.wordpress.com/2010/04/15/k-isolated-sat/" rel="nofollow">$k$-ISOLATED SAT</a> be the problem which requires deciding whether the input CNF formula has a solution that is $k$-isolated.  If $n$ denotes the number of variables in an instance, then $USAT_{\bot}$ and $n$-ISOLATED SAT are precisely the same problem.</p>

<p>For any $\epsilon > 0$, by duplicating each variable polynomially many times, a <em>deterministic</em> reduction can be made from SAT to $n^{1-\epsilon}$-isolated SAT.  (Details are available <a href="http://constraints.wordpress.com/2010/04/15/k-isolated-sat/" rel="nofollow">here</a>.)  This seems to provide further evidence that the gap between deterministic and randomized reductions is "small".</p>

CC BY-SA 3.0
2012-11-22T10:56:15.063Z
I would say this is evidence against P=RP. Analogously, the assumption $P\neq NP$ is supported by the fact that many good approximation algorithms are matched by NP-hardness results - if $P=NP$ it is difficult to explain why the techniques stop exactly at this small or non-existent gap.
Colin McQuillan
CC BY-SA 3.0
2012-11-24T17:34:37.370Z
@Colin: No comment.  :-)
András Salamon
CC BY-SA 2.5
2010-08-16T23:36:51.073Z
2010-08-16T23:36:51.073Z
András Salamon
<p>The existence of problems in DTIME(2^O(n)) which require exponential-size circuits to compute (which is the assumption in IW) seems plausible since otherwise we would have non-uniformity giving a speedup on EVERY computational problem -- which goes completely against the current thinking that does not see a "too significant" gap between uniform and non-uniform complexity for "normal" problems.  This thinking comes from the fact that there are very few examples where a "non-uniform" algorithm is known that is significantly better than the known uniform one (again except for derandomization).</p>

<p>Another piece of "evidence" is that relative to a <em>random</em> oracle we do have P=BPP.</p>

CC BY-SA 2.5
2010-08-17T17:50:43.817Z
I thought that was the precise paper I mentioned in the original question.  What am I missing?
András Salamon
CC BY-SA 2.5
2010-08-17T18:37:35.080Z
oops, i guess i didn't read the question all the way...

The reason that the assumption is plausible is that otherwise we would have non-uniformity giving a speedup on EVERY computational problem -- which goes completely against the current thinking that does not see a "too significant" gap between uniform and non-uniform complexity for "normal" problems.
Noam
CC BY-SA 2.5
2010-08-17T18:59:43.163Z
edited the response now --- still getting to know the system...
Noam
CC BY-SA 2.5
2010-08-17T17:21:13.977Z
2010-08-17T18:58:51.980Z
2010-08-17T18:58:51.980Z
Noam
<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#rp" rel="noreferrer">RP</a> is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error.  P is the usual class of problems decidable by a deterministic Turing machine that terminates in polynomial time.</p>

<p>P = RP follows from a relationship in circuit complexity.  Impagliazzo and Wigderson showed that P = BPP follows <a href="http://doi.acm.org/10.1145/258533.258590" rel="noreferrer">if some problem that can be decided in deterministic exponential time also requires exponential size circuits</a> (note that P = BPP implies P = RP).  Perhaps due to these results, there seems to be a feeling among some complexity theorists that probabilistic reductions can probably be derandomized.</p>

<blockquote>
  <p>What other <em>specific</em> evidence is there that P = RP?</p>
</blockquote>

CC BY-SA 2.5
2010-08-23T15:46:14.280Z
See also a related question http://cstheory.stackexchange.com/questions/364/what-evidence-is-there-that-corp-neq-np
András Salamon
<cc.complexity-theory><derandomization><conditional-results><randomized-algorithms>
What specific evidence is there for P = RP?
András Salamon
# What specific evidence is there for P = RP?

(Asked by: username_0 on 2010-08-16)

[RP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#rp) is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by a deterministic Turing machine that terminates in polynomial time.

P = RP follows from a relationship in circuit complexity. Impagliazzo and Wigderson showed that P = BPP follows [if some problem that can be decided in deterministic exponential time also requires exponential size circuits](http://doi.acm.org/10.1145/258533.258590) (note that P = BPP implies P = RP). Perhaps due to these results, there seems to be a feeling among some complexity theorists that probabilistic reductions can probably be derandomized.

> What other *specific* evidence is there that P = RP?

**Tags:** cc.complexity-theory, derandomization, conditional-results, randomized-algorithms
> **Comments:**
> **username_0**: See also a related question http://cstheory.stackexchange.com/questions/364/what-evidence-is-there-that-corp-neq-np  

---

## 4 answers

### Answer by username_4 on 2010-08-17. Score: 14 | Accepted answer

The existence of problems in DTIME(2^O(n)) which require exponential-size circuits to compute (which is the assumption in IW) seems plausible since otherwise we would have non-uniformity giving a speedup on EVERY computational problem -- which goes completely against the current thinking that does not see a "too significant" gap between uniform and non-uniform complexity for "normal" problems. This thinking comes from the fact that there are very few examples where a "non-uniform" algorithm is known that is significantly better than the known uniform one (again except for derandomization).

Another piece of "evidence" is that relative to a *random* oracle we do have P=BPP.

> **Comments:**
> **username_0**: I thought that was the precise paper I mentioned in the original question.  What am I missing?  
> **username_4**: oops, i guess i didn't read the question all the way...  The reason that the assumption is plausible is that otherwise we would have non-uniformity giving a speedup on EVERY computational problem -- which goes completely against the current thinking that does not see a "too significant" gap between uniform and non-uniform complexity for "normal" problems.  
> **username_4**: edited the response now --- still getting to know the system...  

---

### Answer by username_1 on 2010-08-16. Score: 11

Any concrete derandomization result gives evidence that P=BPP. As such PRIMES in P (Agrawal-Kayal-Saxena'02) is one good example. Generally, there are few natural problems in BPP that are not known to be in P (Polynomial Identity Testing is one notable exception.)

Similar in spirit to the result you mention, Hastad-Impagliazzo-Levin-Luby '99 showed that the existence of one-way functions implies the existence of pseudorandom generators. While this does not directly imply P=BPP based on the existence of one-way functions, it does show that pseudorandom generators follow from minimal cryptographic assumptions. This may be seen as another hint that BPP is not more powerful than P.


---

### Answer by username_2 on 2010-08-17. Score: 8

It's important to note that saying "probabilistic reductions can [probably] be derandomized" is much stronger than P=RP. In fact, one formalization of the notion of derandomizing all randomized reductions is that $P^X=RP^X$ *relative to every oracle $X$*, which we know is false (e.g. Heller. Relativized polynomial hierarchies extending two levels, Mathematical Systems Theory 17(2):71-84, 1984 gives an oracle where $ZPP=RP=EXP$ which is not equal to $P$ by the Time Hierarchy Theorem).

The above is, of course, talking about derandomizing randomized polynomial-time Turing reductions, rather than the usual polynomial-time many-one reductions. I wouldn't be surprised if Heller's oracle can be adapted to give a set X such that for all Y, Y is exponential-time many-one reducible to X iff Y is RP-reducible to X, but without going through the construction I couldn't swear to it.


---

### Answer by username_0 on 2010-08-16. Score: 5

[Valiant and Vazirani showed in 1986](http://dx.doi.org/10.1016/0304-3975%2886%2990135-0) that there is a randomized reduction of SAT to $USAT\_Q$, which is the decision problem based on SAT where only the difference between satisfiable and unsatisfiable instances matters. If $Q = \bot$ is the false predicate, then $USAT\_{\bot}$ is the problem of deciding whether there is precisely one solution.

A solution to a Boolean formula $\phi$ is a (0,1)-vector assigning truth values to the free variables in $\phi$, so that $\phi$ is satisfied. A $k$-isolated solution $x$ to $\phi$ is a solution, with the additional property that any other solution differs in more than $k$ values. (Alternately, $x$ is a $k$-isolated solution if the Hamming distance of $x$ to any other solution exceeds $k$.)

Let [$k$-ISOLATED SAT](http://constraints.wordpress.com/2010/04/15/k-isolated-sat/) be the problem which requires deciding whether the input CNF formula has a solution that is $k$-isolated. If $n$ denotes the number of variables in an instance, then $USAT\_{\bot}$ and $n$-ISOLATED SAT are precisely the same problem.

For any $\epsilon > 0$, by duplicating each variable polynomially many times, a *deterministic* reduction can be made from SAT to $n^{1-\epsilon}$-isolated SAT. (Details are available [here](http://constraints.wordpress.com/2010/04/15/k-isolated-sat/).) This seems to provide further evidence that the gap between deterministic and randomized reductions is "small".

> **Comments:**
> **username_3**: I would say this is evidence against P=RP. Analogously, the assumption $P\neq NP$ is supported by the fact that many good approximation algorithms are matched by NP-hardness results - if $P=NP$ it is difficult to explain why the techniques stop exactly at this small or non-existent gap.  
> **username_0**: @Colin: No comment.  :-)  

---

