文章基本信息

标题：Polynomial Space Randomness in Analysis
本地全文：下载
作者：Xiang Huang ; Donald M. Stull
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：58
页码：86:1-86:13
DOI：10.4230/LIPIcs.MFCS.2016.86
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the interaction between polynomial space randomness and a fundamental result of analysis, the Lebesgue differentiation theorem. We generalize Ko's framework for polynomial space computability in R^n to define weakly pspace-random points, a new variant of polynomial space randomness. We show that the Lebesgue differentiation theorem characterizes weakly pspace random points. That is, a point x is weakly pspace random if and only if the Lebesgue differentiation theorem holds for a point x for every pspace L_1-computable function.
关键词：algorithmic randomness; computable analysis; resource-bounded randomness; complexity theory