Hardness vs randomness. (English) Zbl 0821.68057

Summary: We present a simple new construction of a pseudorandom bit generator. It stretches a short string of truly random bits into a long string that looks random to any algorithm from a complexity class \(C\) (e.g., \(P\), \(NC\), \(PSPACE\),…) using an arbitrary function that is hard for \(C\). This construction reveals an equivalence between the problem of proving lower bounds and the problem of generating good pseudorandom sequences. Our construction has many consequences. The most direct one is that efficient deterministic simulation of randomized algorithms is possible under much weaker assumptions than previously known. The efficiency of the simulations depends on the strength of the assumptions, and may achieve \(P = BPP\). We believe that our results are very strong evidence that the gap between randomized and deterministic complexity is not large. Using the known lower bounds for constant depth circuits, our construction yields an unconditionally proven pseudorandom generator for constant depth circuits. As an application of this generator we characterize the power of NP with a random oracle.


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
65C10 Random number generation in numerical analysis
Full Text: DOI


[1] Ajtai, M.; Wigderson, A., Deterministic simulation of Probabilistic constant depth circuits, (26th FOCS (1985)), 11-19
[2] Babai, L., Trading group theory for randomness, (17th STOC (1975)), 421-429
[3] Bennet, C. H.; Gill, J., Relative to a random oracle \(A\), \(P^A\)\(NP^A\)Co\(NA^A\) with probability 1, SIAM J. Comput., 10 (1981)
[4] Babai, L.; Moran, S., Arthur Merlin games: A randomized proof system, and a hierarchy of complexity classes, J. Comput. System Sci., 36, No. 2, 254-276 (1988) · Zbl 0652.03029
[5] Babai, L.; Fortnow, L.; Nisan, N.; Wigderson, A., BPP has weak subesponential simulations unless EXPTIME has publishable proofs, (Proceedings, Structures in Complexity Theory (1991)) · Zbl 0802.68054
[6] Boppana, R.; Hirschfield, R., Pseudorandom generators and complexity classes, (Micali, S., Randomness and Computation, Vol. 5 (1989), Adv. in Comput. Res., JAI Press), 1-26
[7] Blum, M.; Micali, S., How to generate cryptographically strong sequences of pseudo random bits, (3rd FOCS (1982)), 112-117 · Zbl 0547.68046
[8] Babai, L.; Nisan, N.; Szegedy, M., Multiparty protocols and logspace hard pseudorandom sequences, (21 st STOC (1989)), 1-11
[9] Chandra, A.; Kozen, D.; Stockmeyer, L., Alternation, J. Assoc. Comput. Mach., 28 (1981) · Zbl 0473.68043
[10] Furst, M.; Lipton, R. J.; Stockmeyer, L., Pseudo random number generation and space complexity, Inform. and Control, 64 (1985)
[11] Goldwasser, S.; Micali, S., Probabilistic encryption, J. Comput. System Sci., 28, No. 2 (1984) · Zbl 0563.94013
[12] Goldwasser, S.; Sipser, M., Private coins vs public coins in interactive proof systems, (18th STOC (1986)), 59-68
[13] Hastad, J., Computational Limitations for Small Depth Circuits, (Ph.D. thesis (1986), MIT Press: MIT Press Greenwich)
[14] Hopcroft, J.; Paul, W.; Valiant, L., On time versus space and related problems, (16th FOCS (1975))
[15] Imagliazzo, R.; Levin, L.; Luby, M., Pseudorandom generators from any one-way function, (21st STOC (1989))
[16] Karp, R. M.; Lipton, R., Turing machines that thake advice, Enseign. Math., 28, 191-209 (1982) · Zbl 0529.68025
[17] Karp, R. M.; Kuby, M., Monte-Carlo algorithms for enumeration and reliability problems, (24th FOCS (1983)), 56-64
[18] Kurtz, S. A., A note on randomized polynomial time, SIAM J. Comput., 16, No. 5 (1987) · Zbl 0634.68041
[19] Nisan, N., Pseudo random bits for constant depth circuits, Combinatorica, 11, No. 1, 63-70 (1991) · Zbl 0732.68056
[20] Reif, J. H.; Tygar, J. D., Towards a Theory of Parallel Randomized Computation (1984), Aiken Computation Lab., Harvard University: Aiken Computation Lab., Harvard University Cambridge, MA, TR-07-84
[21] Sipser, M., A complexity theoretic approach to randomness, (15th STOC (1983)), 330-335
[22] Sipser, M., Expanders, Randomness, or Time vs Space, (Goos, G.; Hartmanis, J., Structure in Complexity Theory, Lecture notes in Computer Science (1986), Springer-Verlag), 325-329, No. 223
[23] Shamir, A., On the generation of cryptographically strong pseudo-random sequences, (8th ICALP, Lecture Notes in Comput. Sci., Vol. 62 (1981), Springer-Verlag: Springer-Verlag New York/Berlin), 544-550
[24] Stockmeyer, L., The polynomial time hierarchy, Theoret. Comput. Sci., 3, No.1 (1976)
[25] Yao, A. C., Theory and applications of trapdoor functions, (23rd FOCS (1982)), 80-91
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.