Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR08-037 | 19th May 2009 00:00

Curves That Must Be Retraced

RSS-Feed




Revision #1
Authors: Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo
Accepted on: 19th May 2009 00:00
Downloads: 3047
Keywords: 


Abstract:

We exhibit a polynomial time computable plane curve GAMMA that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f retraces at least n times. In contrast, every computable curve of finite length that does not intersect itself has a constant-speed (hence non-retracing) parametrization that is computable relative to the halting problem.


Paper:

TR08-037 | 29th February 2008 00:00

Curves That Must Be Retraced





TR08-037
Authors: Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo
Publication: 24th March 2008 22:01
Downloads: 2920
Keywords: 


Abstract:

We exhibit a polynomial time computable plane curve GAMMA that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f retraces at least n times. In contrast, every computable curve of finite length that does not intersect itself has a constant-speed (hence non-retracing) parametrization that is computable relative to the halting problem.



ISSN 1433-8092 | Imprint