zbMATH — the first resource for mathematics

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, (), 11-19
[2] Babai, L., Trading group theory for randomness, (), 421-429
[3] Bennet, C.H.; Gill, J., Relative to a random oracle A, PA≠NPA≠co − NAA 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, () · Zbl 0802.68054
[6] Boppana, R.; Hirschfield, R., Pseudorandom generators and complexity classes, (), 1-26
[7] Blum, M.; Micali, S., How to generate cryptographically strong sequences of pseudo random bits, (), 112-117 · Zbl 0547.68046
[8] Babai, L.; Nisan, N.; Szegedy, M., Multiparty protocols and logspace hard pseudorandom sequences, (), 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, (), 59-68
[13] Hastad, J., Computational limitations for small depth circuits, ()
[14] Hopcroft, J.; Paul, W.; Valiant, L., On time versus space and related problems, ()
[15] Imagliazzo, R.; Levin, L.; Luby, M., Pseudorandom generators from any one-way function, ()
[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, (), 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 Cambridge, MA, TR-07-84
[21] Sipser, M., A complexity theoretic approach to randomness, (), 330-335
[22] Sipser, M., Expanders, randomness, or time vs space, (), 325-329, No. 223
[23] Shamir, A., On the generation of cryptographically strong pseudo-random sequences, (), 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, (), 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.