Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL-TIME COMPUTABLE CURVE:
Reports tagged with polynomial-time computable curve:
TR08-037 | 29th February 2008
Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

Curves That Must Be Retraced

Revisions: 1

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 ... more >>>




ISSN 1433-8092 | Imprint