<p>There are some theorems that state $P = BPP$ if some condition is satisfied. For example, a theorem of Impagliazzo and Wigderson states tha $P=BPP$ unless $DTIME(2^{O(n)})$ has sub-exponential circuits for infinitely many input lengths. </p>

<p>Hence there is a polynomial time deterministic algorithm thet solves the Polynomial Identity Testing problem, that works correctly if this condition ($DTIME (2^{O(n)})$ does not have sub-exponential circuits) is satisfied. </p>

<p>Can one state this algorithm explicitly?</p>

CC BY-SA 3.0
2016-04-07T18:53:29.240Z
Please edit the title to be more related to your question (like "Derandomization of Polynomial Identity Testing")
didest
CC BY-SA 3.0
2016-04-07T19:03:38.697Z
The Impagliazzo–Wigderson theorem is that P=BPP unless each problem in E has subexponential circuits *for infinitely many input lengths*, not everywhere.
Emil Jeřábek
CC BY-SA 3.0
2016-04-07T19:12:43.230Z
Anyway, it’s not clear to me what the question is after. The proof of the theorem is perfectly constructive, so it gives an explicit algorithm: viz. the usual Ibarra–Moran PIT algorithm based on the Schwartz–Zippel–DeMillo–Lipton lemma, with pseudorandom bits supplied by the Nisan–Wigderson generator, whose “hard function” will be an error-corrected version of a language from E that requires exponential circuits. Do you want something else?
Emil Jeřábek
<cc.complexity-theory><derandomization>
Derandomization of Polynomial Identity Testing
Alexey Milovanov
# Derandomization of Polynomial Identity Testing

(Asked by: username_0 on 2016-04-07)

There are some theorems that state $P = BPP$ if some condition is satisfied. For example, a theorem of Impagliazzo and Wigderson states tha $P=BPP$ unless $DTIME(2^{O(n)})$ has sub-exponential circuits for infinitely many input lengths.

Hence there is a polynomial time deterministic algorithm thet solves the Polynomial Identity Testing problem, that works correctly if this condition ($DTIME (2^{O(n)})$ does not have sub-exponential circuits) is satisfied.

Can one state this algorithm explicitly?

**Tags:** cc.complexity-theory, derandomization

> **Comments:**
> **username_1**: Please edit the title to be more related to your question (like "Derandomization of Polynomial Identity Testing")  
> **username_2**: The Impagliazzo–Wigderson theorem is that P=BPP unless each problem in E has subexponential circuits *for infinitely many input lengths*, not everywhere.  
> **username_2**: Anyway, it’s not clear to me what the question is after. The proof of the theorem is perfectly constructive, so it gives an explicit algorithm: viz. the usual Ibarra–Moran PIT algorithm based on the Schwartz–Zippel–DeMillo–Lipton lemma, with pseudorandom bits supplied by the Nisan–Wigderson generator, whose “hard function” will be an error-corrected version of a language from E that requires exponential circuits. Do you want something else?  

---

## 0 answers

