We can use Schwartz-Zippel Lemma to give a randomized polynomial-time algorithm for PIT.The real question is whether we have a deterministic polynomial-time algorithm.In complexity language, we know that PIT is in BPP,and wonder whether it's also in P. A nice (and recent)survey on arithmetic circuit complexity is [SY09],where you canalso find positive and negative results on algorithms for PI'T. References [LZ77]Richard J.Lipton and Yechezkel Zalcstein,Word Problems Solvable in Logspace,Journal ofthe ACM,1977. [SY09]Amir Shpilka and Amir Yehudayoff,Arithmetic Circuits:A Survey of Recent Results and Open Questions,Foundations and Trends in Theoretical Computer Science,Vol.5,Nos.3-4,207- 388,2009 [Val84]Leslie Valiant.Short monotone formulae for the majority function.Journal ofAlgorithms 5(3)363-366,1984We can use Schwartz-Zippel Lemma to give a randomized polynomial-time algorithm for PIT. The real question is whether we have a deterministic polynomial-time algorithm. In complexity language, we know that PIT is in BPP, and wonder whether it’s also in P. A nice (and recent) survey on arithmetic circuit complexity is [SY09], where you can also find positive and negative results on algorithms for PIT. References [LZ77] Richard J. Lipton and Yechezkel Zalcstein, Word Problems Solvable in Logspace, Journal of the ACM, 1977. [SY09] Amir Shpilka and Amir Yehudayoff , Arithmetic Circuits: A Survey of Recent Results and Open Questions, Foundations and Trends in Theoretical Computer Science, Vol. 5, Nos. 3–4, 207– 388, 2009. [Val84] Leslie Valiant. Short monotone formulae for the majority function. Journal of Algorithms 5 (3): 363–366, 1984