Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
On the Complexity of Computing the Logarithm and Square Root Functions on a Complex Domain
verfasst von : Ker-I Ko, Fuxiang Yu
Erschienen in: Computing and Combinatorics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\partial 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
P
MP
and lower bound
P
⊕ P
. That is, if
P
=
MP
then the square root problem is polynomial-time solvable, and if
$P\not= \oplus P$
then the square root problem is not polynomial-time solvable.