<p>If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds.</p>

<blockquote>
  <ol>
  <li>What are the best statements we have proved that come close to converse to these statements?</li>
  </ol>
</blockquote>

<p>My motivation is this $P=BPP$ and $NP\subseteq P/poly$ are consistent with what we know. However $MCSP\subseteq NP\implies$ $NP\subseteq P/poly$ gives no strong pseudorandom generators in $P/poly$ from <a href="https://www.cs.sfu.ca/~kabanets/Research/circuit.html" rel="nofollow noreferrer">Circuit Minimization Problem by Kabanets and Cai</a>.</p>

<blockquote>
  <ol start="2">
  <li>So is it possible one way functions and pseudorandom number generators are not necessary for derandomization? </li>
  </ol>
</blockquote>

<p>It might be that any argument that shows $P=BPP$ implies strong pseudorandom number generator exists should also show $NP\not\subseteq P/poly$ in that case $P=BPP$ and $NP\subseteq P/poly$ should not be consistent with what we know. However I cannot uncover a statement on this.</p>

<p>In an extreme it can very well be that $P=NP$ in which case we have derandomization and no one way functions and pseudorandom number generators. It is not at all clear why these should be considered essential for derandomization.</p>

<blockquote>
  <ol start="3">
  <li>Are there alternate proofs of $E$ needing exponential circuits for infinite input lengths leading to $P=BPP$ without going through these objects?</li>
  </ol>
</blockquote>

CC BY-SA 3.0
2017-12-11T00:00:12.047Z
"In a World of P=BPP" by Oded Goldreich argues that BPP=P implies existence of some form of PRGs. http://www.wisdom.weizmann.ac.il/~oded/PDF/bpp.pdf However, "some form" is technical so I think it is worth reading the details (e.g. the PRGs run in more time, though still polynomial, than the machines it can fool). A more technical summary of the paper might make one good answer to this question ... but I also don't know if it's the last word on that subject.
usul
CC BY-SA 3.0
2017-12-11T00:31:34.490Z
@usul I have made some updates. I am not at all convinced $P=BPP$ implies strong PRGs.
Turbo
CC BY-SA 3.0
2017-12-11T06:08:19.230Z
@usul the key could be 'PRGs in class $P/poly$ under some conditions'. I think $P=BPP$ is consistent with no strong PRGs in $P/poly$ if $E\not\subseteq P/poly$ (which means $P=BPP$ and $MCSP\subseteq NP\subseteq P/poly$ and $E\not\subseteq P/poly$ is possible) but not consistent with no strong PRGs in $P/poly$ if if $E\subseteq P/poly$ (which means $P=BPP$ and $MCSP\subseteq NP\subseteq E\subseteq P/poly$ is not possible).
Turbo
CC BY-SA 3.0
2017-12-12T12:22:22.153Z
Are you aware of Kabanets and Impagliazzo’s paper “Derandomizing Polynomial Identity Tests means proving circuit lower bounds”?
Emil Jeřábek
CC BY-SA 3.0
2017-12-12T12:27:15.640Z
$PIT\in P\implies NEXP\not\subseteq P/poly\mbox{ or }Perm\not\in AlgP/Poly$?
Turbo
<cc.complexity-theory><big-picture><derandomization><pseudorandom-generators><one-way-function>
Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?
Turbo
# Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?

(Asked by: username_0 on 2017-12-06)

If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds.

> 1. What are the best statements we have proved that come close to converse to these statements?

My motivation is this $P=BPP$ and $NP\subseteq P/poly$ are consistent with what we know. However $MCSP\subseteq NP\implies$ $NP\subseteq P/poly$ gives no strong pseudorandom generators in $P/poly$ from [Circuit Minimization Problem by Kabanets and Cai](https://www.cs.sfu.ca/~kabanets/Research/circuit.html).

> 2. So is it possible one way functions and pseudorandom number generators are not necessary for derandomization?

It might be that any argument that shows $P=BPP$ implies strong pseudorandom number generator exists should also show $NP\not\subseteq P/poly$ in that case $P=BPP$ and $NP\subseteq P/poly$ should not be consistent with what we know. However I cannot uncover a statement on this.

In an extreme it can very well be that $P=NP$ in which case we have derandomization and no one way functions and pseudorandom number generators. It is not at all clear why these should be considered essential for derandomization.

> 3. Are there alternate proofs of $E$ needing exponential circuits for infinite input lengths leading to $P=BPP$ without going through these objects?

**Tags:** cc.complexity-theory, big-picture, derandomization, pseudorandom-generators, one-way-function

> **Comments:**
> **username_1**: "In a World of P=BPP" by Oded Goldreich argues that BPP=P implies existence of some form of PRGs. http://www.wisdom.weizmann.ac.il/~oded/PDF/bpp.pdf However, "some form" is technical so I think it is worth reading the details (e.g. the PRGs run in more time, though still polynomial, than the machines it can fool). A more technical summary of the paper might make one good answer to this question ... but I also don't know if it's the last word on that subject.  
> **username_0**: @username_1 I have made some updates. I am not at all convinced $P=BPP$ implies strong PRGs.  
> **username_0**: @username_1 the key could be 'PRGs in class $P/poly$ under some conditions'. I think $P=BPP$ is consistent with no strong PRGs in $P/poly$ if $E\not\subseteq P/poly$ (which means $P=BPP$ and $MCSP\subseteq NP\subseteq P/poly$ and $E\not\subseteq P/poly$ is possible) but not consistent with no strong PRGs in $P/poly$ if if $E\subseteq P/poly$ (which means $P=BPP$ and $MCSP\subseteq NP\subseteq E\subseteq P/poly$ is not possible).  
> **username_2**: Are you aware of Kabanets and Impagliazzo’s paper “Derandomizing Polynomial Identity Tests means proving circuit lower bounds”?  
> **username_0**: $PIT\in P\implies NEXP\not\subseteq P/poly\mbox{ or }Perm\not\in AlgP/Poly$?  

---

## 0 answers

