On the complexity of computing the logarithm and square root functions on a complex domain

AbstractThe 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 ∂S 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 polynomial-time solvable, and if P≠⊕P then the square root problem is not polynomial-time solvable