Pseudorandom number generation and space complexity

DOI10.1016/S0019-9958(85)80043-7zbMath0575.68048MaRDI QIDQ3694692

Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer

Publication date: 1985

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

bipartite graphmatchingdiscrete logarithm problemintractabilityspace complexitydeterministic simulationpolynomial time probabilistic Turing machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random number generation in numerical analysis (65C10)

Related Items

Hardness vs randomness, Pseudorandom bits for constant depth circuits