2026-08-10T22:48:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4491 2024-03-06T10:35:08Z ddc:004 open_access

Differentiability of polynomial time computable functions Nies, André Polynomial time randomness feasible analysis differentiability porosity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik André Nies 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.602 urn:nbn:de:0030-drops-44919 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.602 eng https://creativecommons.org/licenses/by/3.0/legalcode