On the Complexity of Computing the Logarithm and Square Root Functions on a Complex Domain

摘要

The problems of computing single-valued, analytic branches of the logarithm and square root functions on a bounded, simply connected domain S are studied. If the boundary dS of S is a polynomial-time computable Jordan curve, the complexity of these problems can be characterized by counting classes #P, MP (or MidBitP), and ⊕P: The logarithm problem is polynomial-time solvable if and only if FP=#P. For the square root problem, it has been shown to have the upper bound PMP and lower bound P⊕P. That is, if P=MP then the square root problem is polynomialtime solvable, and if P ≠ ⊕P then the square root problem is not polynomial-time solvable.