Functions that preserve p-randomness

Details Functions that preserve p-randomness Functions that preserve p-randomness

2012-02-28

arxiv.org/abs/1202.6395v1

Computer Science

Computational Complexity

24 pages, 2 figures. An extended abstract of this paper appeared in Proceedings of the 18th International Symposium on Fundame

Scientific paper

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 \ne r$, or (b) $(f(x) - f(r))(x-r) < -C$ for all $x$ in $I$ with $x \ne 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.

Affiliated with

Also associated with

No associations

Rating

Functions that preserve p-randomness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Functions that preserve p-randomness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Functions that preserve p-randomness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-522914