On the Complezity of Computing the Logarithm and Square Root Functions on a Complez 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.

作者: Ker-I Ko Fuxiang Yu

作者单位: Department of Computer Science State University of New York at Stony Brook Stony Brook, NY 11794, USA

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 349-358

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）