Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Nies, André http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-44919
URL:

Differentiability of polynomial time computable functions

pdf-format:


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
Seminar: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue date: 2014
Date of publication: 2014


DROPS-Home | Fulltext Search | Imprint Published by LZI