文章基本信息

标题：Differentiability of polynomial time computable functions
本地全文：下载
作者：Andr{\'e} Nies
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：25
页码：602-613
DOI：10.4230/LIPIcs.STACS.2014.602
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Polynomial time randomness; feasible analysis; differentiability; porosity