2012/02/28 by Stephen Fenner, Stephen A. Fenner, Fenner, Stephen A.
Computer Science · Mathematics · #Algorithms and Data Compression #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.2.1 #F.2.2 #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1202.6395
24 pages, 2 figures. An extended abstract of this paper appeared in Proceedings of the 18th International Symposium on Fundamentals of Computation Theory (FCT), volume 6914 of Lecture Notes in Computer Science, Springer-Verlag, pages 336-347, 2011
arxiv created 2012/02/28 · openalex publication_date 2012/02/28 · arxiv updated 2012/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that polynomial-time randomness (p-randomness) is preserved under a variety of familiar operations, including addition and multiplication by a nonzero polynomial-time computable real number. These results follow from a general theorem: If I is an open interval in the reals, f is a function mapping I into the reals, and r in I is p-random, then f(r) is p-random provided 1. f is p-computable on the dyadic rational points in I, and 2. f varies sufficiently at r, i.e., there exists a real constant C > 0 such that either (a) (f(x) - f(r))/(x-r) > C for all x in I with x ≠ r, or (b) (f(x) - f(r))(x-r) < -C for all x in I with x ≠ r. Our theorem implies in particular that any analytic function about a p-computable point whose power series has uniformly p-computable coefficients preserves p-randomness in its open interval of absolute convergence. Such functions include all the familiar functions from first-year calculus.