OASIcs.CCA.2009.2272.pdf
- Filesize: 353 kB
- 12 pages
Document
Towards the Complexity of Riemann Mappings (Extended Abstract)
Author
-
Part of:
Volume:
6th International Conference on Computability and Complexity in Analysis (CCA'09) (CCA 2009)
Series: Open Access Series in Informatics (OASIcs) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2009-11-25
Cite As Get BibTex
Robert Rettinger. Towards the Complexity of Riemann Mappings (Extended Abstract). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 209-220, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/OASIcs.CCA.2009.2272
Abstract
We show that under reasonable assumptions there exist Riemann mappings which are as hard as tally $\sharp$-P even in the non-uniform case. More precisely, we show that under a widely accepted conjecture from numerical mathematics there exist single domains with simple, i.e. polynomial time computable, smooth boundary whose Riemann mapping is polynomial time computable if and only if tally $\sharp$-P equals P. Additionally, we give similar results without any assumptions using tally $UP$ instead of $\sharp$-P and show that Riemann mappings of domains with polynomial time computable analytic boundaries are polynomial time computable.
Subject Classification
Keywords
- Riemann mapping
- complexity
- polynomial time
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads