On parallel complexity of analytic functions
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
57 | en_US |
dc.citation.issue |
en_US | |
dc.citation.spage |
48 | en_US |
dc.citation.volume |
489 | en_US |
dc.citation.woscount |
0 | |
dc.contributor.author |
Yu, Fuxiang | en_US |
dc.contributor.author |
Ko, Ker-I | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.date.accessioned |
2014-12-08T15:31:23Z | |
dc.date.available |
2014-12-08T15:31:23Z | |
dc.date.issued |
2013-06-10 | en_US |
dc.description.abstract |
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. | en_US |
dc.identifier.doi |
10.1016/j.tcs.2013.04.008 | en_US |
dc.identifier.issn |
0304-3975 | en_US |
dc.identifier.journal |
THEORETICAL COMPUTER SCIENCE | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/j.tcs.2013.04.008 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/22298 | |
dc.identifier.wosnumber |
WOS:000320973900004 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Complexity | en_US |
dc.subject |
Analytic functions | en_US |
dc.subject |
Logarithmic space | en_US |
dc.subject |
NC | en_US |
dc.subject |
Derivatives | en_US |
dc.subject |
Integration | en_US |
dc.subject |
Zero-finding | en_US |
dc.title |
On parallel complexity of analytic functions | en_US |
dc.type |
Article | en_US |
檔案
- 000320973900004.pdf (413.2 KB, Adobe PDF)
所屬典藏: 期刊論文