<p>A famous theorem due to Impagliazzo and Wigderson states that if some function in $E=DTIME[2^{O(n)}]$ requires circuits of size $2^{\Omega(n)}$ then P=BPP. </p>

<p>When can we change $P$ with some complexity class $C$ such that the same result works? In other words, for which complexity classes the following statement is true?</p>

<p><strong>Statement:</strong> If some function in $E$ requires circuits of size $2^{\Omega(n)}$ then $C= BP-C$. </p>

<p>Here $BP-C$ is the bounded probabilistic version of $C$.</p>

<p>In particular does it work for formulas? I.e. for $C$ equal to logspace uniform $NC_1$ ? In this case the statement would be: </p>

<p>If some function in E requires formulas of size $2^{\Omega(n)}$ then $NC_1 = BP-NC_1$</p>

CC BY-SA 3.0
2018-02-18T14:29:04.243Z
I haven't checked the details, but at least you need to scale E down as well: if you want to derandomize NC^1 in place of P,  you need ATIME(O(n)) in place of E (i.e., the exponentially scaled version of NC^1).
Emil Jeřábek
CC BY-SA 3.0
2018-02-19T18:20:23.223Z
I recommend you check out the paper ["Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses"](http://epubs.siam.org/doi/abs/10.1137/S0097539700389652) by Klivans and van Melkebeek.
William Hoza
<cc.complexity-theory><circuit-complexity><derandomization><pseudorandomness>
Scaled down and scaled up versions of Impagliazzo-Wigderson Therem
verifying
# Scaled down and scaled up versions of Impagliazzo-Wigderson Therem

(Asked by: username_0 on 2018-02-17)

A famous theorem due to Impagliazzo and Wigderson states that if some function in $E=DTIME[2^{O(n)}]$ requires circuits of size $2^{\Omega(n)}$ then P=BPP.

When can we change $P$ with some complexity class $C$ such that the same result works? In other words, for which complexity classes the following statement is true?

**Statement:** If some function in $E$ requires circuits of size $2^{\Omega(n)}$ then $C= BP-C$.

Here $BP-C$ is the bounded probabilistic version of $C$.

In particular does it work for formulas? I.e. for $C$ equal to logspace uniform $NC\_1$ ? In this case the statement would be:

If some function in E requires formulas of size $2^{\Omega(n)}$ then $NC\_1 = BP-NC\_1$

**Tags:** cc.complexity-theory, circuit-complexity, derandomization, pseudorandomness
> **Comments:**
> **username_1**: I haven't checked the details, but at least you need to scale E down as well: if you want to derandomize NC^1 in place of P,  you need ATIME(O(n)) in place of E (i.e., the exponentially scaled version of NC^1).  
> **username_2**: I recommend you check out the paper ["Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses"](http://epubs.siam.org/doi/abs/10.1137/S0097539700389652) by Klivans and van Melkebeek.  

---

## 0 answers

