2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.