License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.602
URN: urn:nbn:de:0030-drops-44919
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4491/
Go to the corresponding LIPIcs Volume Portal

Nies, André

Differentiability of polynomial time computable functions

pdf-format:
49.pdf (0.6 MB)

Abstract

We show that a real z is polynomial time random if and only if each nondecreasing polynomial time computable function is differentiable at z. This establishes an analog in feasible analysis of a recent result of Brattka, Miller and Nies, who characterized computable randomness in terms of differentiability of nondecreasing computable functions.

Further, we show that a Martin-Loef random real z is a density-one point if and only if each interval-c.e. function is differentiable at z. (To say z is a density-one point means that every effectively closed class containing z has density one at z. The interval-c.e. functions are, essentially, the variation functions of computable functions.)

The proofs are related: they both make use of the analytical concept of porosity in novel ways, and both use a basic geometric fact on shifting dyadic intervals by 1/3.

BibTeX - Entry

@InProceedings{nies:LIPIcs:2014:4491,
  author =	{Andr{\'e} Nies},
  title =	{{Differentiability of polynomial time computable functions}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{602--613},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4491},
  URN =		{urn:nbn:de:0030-drops-44919},
  doi =		{10.4230/LIPIcs.STACS.2014.602},
  annote =	{Keywords: Polynomial time randomness, feasible analysis, differentiability, porosity}
}

Keywords: Polynomial time randomness, feasible analysis, differentiability, porosity
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

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