DROPS

Document

Extended Abstract

DOI: 10.4230/OASIcs.CCA.2009.2272

Towards the Complexity of Riemann Mappings (Extended Abstract)

Authors: Robert Rettinger

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{rettinger:OASIcs.CCA.2009.2272,
  author =	{Rettinger, Robert},
  title =	{{Towards the Complexity of Riemann Mappings}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{209--220},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2272},
  URN =		{urn:nbn:de:0030-drops-22724},
  doi =		{10.4230/OASIcs.CCA.2009.2272},
  annote =	{Keywords: Riemann mapping, complexity, polynomial time}
}

Document

Extended Abstract

DOI: 10.4230/OASIcs.CCA.2009.2273

On the Computability of Rectifiable Simple Curve (Extended Abstract)

Authors: Robert Rettinger and Xizhong Zheng

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract

In mathematics curves are defined as the images of continuous real functions defined on closed intervals and these continuous functions are called parameterizations of the corresponding curves. If only simple curves of finite lengths are considered, then parameterizations can be restricted to the injective continuous functions or even to the continuous length-normalized parameterizations. In addition, a plane curve can also be considered as a connected one-dimensional compact subset of points. By corresponding effectivizations, we will introduce in this paper four versions of computable curves and show that they are all different. More interestingly, we show also that four classes of computable curves cover even different sets of points.

Cite as

Robert Rettinger and Xizhong Zheng. On the Computability of Rectifiable Simple Curve (Extended Abstract). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 221-232, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{rettinger_et_al:OASIcs.CCA.2009.2273,
  author =	{Rettinger, Robert and Zheng, Xizhong},
  title =	{{On the Computability of Rectifiable Simple Curve}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{221--232},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2273},
  URN =		{urn:nbn:de:0030-drops-22736},
  doi =		{10.4230/OASIcs.CCA.2009.2273},
  annote =	{Keywords: Computable curve, simple curve, rectifiable curve, point separability}
}

Search Results

Documents authored by Rettinger, Robert

Towards the Complexity of Riemann Mappings (Extended Abstract)

Abstract

Cite as

On the Computability of Rectifiable Simple Curve (Extended Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message