Some consequences of the existence of pseudorandom generators

摘要

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.