Some consequences of the existence of pseudorandom generators

Research output: Contribution to journalArticle

17 Scopus citations

Abstract

This paper introduces a type of generalized Kolmogorov complexity and uses it as a tool to explore the consequences of several assumptions about the existence of secure pseudorandom generators. It is shown that if secure generators exist, then there are fast deterministic simulations of probabilistic algorithms; the nature of the simulations and the class of probabilistic algorithms for which simulations can be exhibited depends on the notion of "security" which is assumed. One goal of the investigation begun here is to show that many important questions in complexity theory may be viewed as questions about the Kolmogorov complexity of sets in P.

Original languageEnglish (US)
Pages (from-to)101-124
Number of pages24
JournalJournal of Computer and System Sciences
Volume39
Issue number1
DOIs
StatePublished - Aug 1989

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this