License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.CCA.2009.2272
URN: urn:nbn:de:0030-drops-22724
Go to the corresponding OASIcs Volume Portal

Rettinger, Robert
Contributed Papers

Towards the Complexity of Riemann Mappings (Extended Abstract)

Rettinger.2272.pdf (0.3 MB)


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

  author =	{Robert Rettinger},
  title =	{{Towards the Complexity of Riemann Mappings  (Extended Abstract)}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Andrej Bauer and Peter Hertling and Ker-I Ko},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-22724},
  doi =		{10.4230/OASIcs.CCA.2009.2272},
  annote =	{Keywords: Riemann mapping, complexity, polynomial time}

Keywords: Riemann mapping, complexity, polynomial time
Collection: 6th International Conference on Computability and Complexity in Analysis (CCA'09)
Issue Date: 2009
Date of publication: 25.11.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI