Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
On Some Complexity Issues of NC Analytic Functions
verfasst von : Fuxiang Yu
Erschienen in: Theory and Applications of Models of Computation
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
This paper studies the complexity of derivatives and integration of
NC
real functions (not necessarily analytic) and
NC
analytic functions. We show that for
NC
real functions, derivatives and integration are infeasible, but analyticity helps to reduce the complexity. For example, the integration of a log-space computable real function
f
is as hard as #
P
, but if
f
is an analytic function, then the integration is log-space computable. As an application, we study the problem of finding all zeros of an
NC
analytic function inside a Jordan curve and show that, under a uniformity condition on the function values of the Jordan curve, the zeros are all
NC
computable.