when quoting this document, please refer to the following
DOI: 10.4230/OASIcs.CCA.2009.2272
URN: urn:nbn:de:0030-drops-22724
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2272/

Rettinger, Robert
Contributed Papers

Towards the Complexity of Riemann Mappings (Extended Abstract)

 pdf-format:

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.

BibTeX - Entry

```@InProceedings{rettinger:DSP:2009:2272,
author =	{Robert Rettinger},
title =	{Towards the Complexity of Riemann Mappings  (Extended Abstract)},
booktitle =	{6th Int'l Conf. on Computability and Complexity in Analysis},
year =	{2009},
editor =	{Andrej Bauer and Peter Hertling and Ker-I Ko},
publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},