On parallel complexity of analytic functions

Abstract

In this paper, we study the parallel complexity of analytic functions. We investigate the complexity of computing the derivatives, integrals, and zeros of NC or logarithmic-space computable analytic functions, where NC denotes the complexity class of sets acceptable by polynomial-size, polylogarithmic-depth, uniform Boolean circuits. It is shown that the derivatives and integrals of NC (or logarithmic-space) computable analytic functions remain NC (or, respectively, logarithmic-space) computable. We also study the problem of finding all zeros of an NC computable analytic function inside an NC computable Jordan curve, and show that, under a uniformity condition on the function values on the Jordan curve, all zeros can be found in NC. (c) 2013 Elsevier B.V. All rights reserved.