2026-07-20T11:16:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2272 2024-03-06T10:28:38Z ddc:004 open_access

Towards the Complexity of Riemann Mappings (Extended Abstract) Rettinger, Robert Riemann mapping complexity polynomial time 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Rettinger 2009 Is Part Of OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.CCA.2009.2272 urn:nbn:de:0030-drops-22724 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2272 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode