×

zbMATH — the first resource for mathematics

How to construct random functions. (English) Zbl 0596.65002
Theory of algorithms, Colloq. Pécs/Hung. 1984, Colloq. Math. Soc. János Bolyai 44, 161-189 (1986).
Summary: [For the entire collection see Zbl 0592.00028.]
A constructive theory of randomness for functions is developed, based on computational complexity. We present a deterministic polynomial-time algorithm that transforms pairs \((g,r)\), where \(g\) is any one-way (in a very weak sense) function and \(r\) is a random \(k\)-bit string, to polynomial-time computable functions \(f_ r:\{1,...2^ k\}\to \{1,...,2^ k\}\). These \(f_ r\)’s cannot be distinguished from random functions by any probabilistic polynomial time algorithm that asks and receives the value of a function at arguments of its choice.
The journal version has been published in J. Assoc. Comput. Mach. 33, No. 4, 792–807 (1986).

MSC:
65C10 Random number generation in numerical analysis
68Q25 Analysis of algorithms and problem complexity
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)