Some consequences of the existence of pseudorandom generators

E Allender

doi:10.1145/28395.28412

Back

Conference proceeding

Some consequences of the existence of pseudorandom generators

E Allender

Proceedings of the nineteenth annual ACM symposium on theory of computing, pp.151-159

STOC '87

01/01/1987

DOI: https://doi.org/10.1145/28395.28412

Abstract

If secure pseudorandom generators exist, then probabilistic computation does not uniformly speed up deterministic computation. If sets in P must contain infinitely many noncomplex strings, then nondeterministic computation does not uniformly speed up deterministic computation. Connections are drawn between pseudorandom generation, generalized Kolmogorov complexity, and immunity properties of complexity classes.

Metrics

6 Record Views

Details

Title: Some consequences of the existence of pseudorandom generators
Creators: E Allender
Publication Details: Proceedings of the nineteenth annual ACM symposium on theory of computing, pp.151-159
Date published: 01/01/1987
Series: STOC '87
Publisher: ACM
Academic Unit: Computer Science (SAS)
Language: English
Resource Type: Conference proceeding
Identifiers: 991031654722304646