On parallel complexity of analytic functions

檔案

日期

2013-06-10

類型

期刊名稱

THEORETICAL COMPUTER SCIENCE

卷期與頁次

第 489 卷,頁 48–57

ISSN

0304-3975

語言

英文

摘要

In this paper, we study the parallel complexity of analytic functions. We investigate the complexity of computing the derivatives, integrals, and zeros of NC or logarithmic-space computable analytic functions, where NC denotes the complexity class of sets acceptable by polynomial-size, polylogarithmic-depth, uniform Boolean circuits. It is shown that the derivatives and integrals of NC (or logarithmic-space) computable analytic functions remain NC (or, respectively, logarithmic-space) computable. We also study the problem of finding all zeros of an NC computable analytic function inside an NC computable Jordan curve, and show that, under a uniformity condition on the function values on the Jordan curve, all zeros can be found in NC. (c) 2013 Elsevier B.V. All rights reserved.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Yu, F., & Ko, K.-I. (2013). On parallel complexity of analytic functions. THEORETICAL COMPUTER SCIENCE, 489, 48–57. https://doi.org/10.1016/j.tcs.2013.04.008

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/22298