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?

  • 1
    $\begingroup$ Please edit the title to be more related to your question (like "Derandomization of Polynomial Identity Testing") $\endgroup$ – Diego de Estrada Apr 7 '16 at 18:53
  • 2
    $\begingroup$ The Impagliazzo–Wigderson theorem is that P=BPP unless each problem in E has subexponential circuits for infinitely many input lengths, not everywhere. $\endgroup$ – Emil Jeřábek Apr 7 '16 at 19:03
  • 4
    $\begingroup$ 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? $\endgroup$ – Emil Jeřábek Apr 7 '16 at 19:12

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.