Kloosterman-type sums and the discrepancy of nonoverlapping pairs of inversive congruential pseudorandom numbers
Kolmogorov complexity, pseudorandom generators and statistical models testing
An attempt to formalize heuristic concepts like strings (sequences resp.) “typical” for a probability measure is stated in the paper. Both generating and testing of such strings is considered. Kolmogorov complexity theory is used as a tool. Classes of strings “typical” for a given probability measure are introduced. It is shown that no pseudorandom generator can produce long strings from the classes. The time complexity of pseudorandom generators with oracles capable to recognize “typical” strings...