On the notion of infinite pseudorandom sequences (Q1091817)

The notion of infinite pseudorandom sequences with respect to polynomial time and polynomial space computability is studied. Three formal definitions of pseudorandom sequences are given, based on the polynomial versions of Martin-Löf tests, Kolmogorov complexity and von Mises's collectives. One of the main results is the study of the polynomial time and polynomial space versions of the Martin-Löf-Levin-Schnorr Theorem which states that an infinite sequence x is Martin-Löf random if and only if it has high monotonic Kolmogorov complexity. The polynomial space version of this theorem is proved, while the polynomial time version is left open with some evidence showing it could be a difficult problem. In order to develop this result, polynomial time/space-bounded Kolmogorov complexity of infinite sequences has also been studied. It is shown that there exists a double exponential time computable sequence which is pseudorandom with respect to polynomial time computability. Similarly to the randomness with respect to recursive computability, von Mises's definition of pseudorandomness is proved to be weaker than the other two definitions, with respect to both polynomial space and polynomial time computability.