Some consequences of the existnce of pseudorandom generators (Q1822961)

A pseudorandom generator (prg) is an efficient routine which takes a short input (the seed) and produces a long output (the pseudorandom number). This paper examines several hypotheses about the security of prg and derives for each hypothesis a necessary condition in terms of Kolmogorov complexity. Since the paper is very technical, a general section by section synopsis is given below followed by the author's summary. After an introduction in section 1 and basic definitions in section 2, prg are defined in section 3 along with the concepts of security, strong security, next bit tests, one way functions and extenders. In the next section Kolmogorov complexity (K complexity) is reviewed and a new measure of security \((K_ L)\) is introduced. Very briefly, for any set \(L=(0+1)*\), \(K_ L(n)\) measures the time bounded K coplexity of the ``simplest'' strings in L of length n. The rest of the sections forms an investigation into the properties of this measure in relation to four hypotheses about security of prg introduced earlier. Typically these hypotheses are shown to have consequences about the growth rate of functions of the type \(K_ L\). In section 6, these growth rates are shown to involve relationships among deterministic, probabilistic and nondeterministic complexity classes. The next section shows that if secure prg exist then sufficiently dense sets in RP satisfy certain ``immunity'' properties. The last section is titled conclusions and is followed by an excellent bibliography on the subject. The author's summary follows: This paper introduces a generalized K complexity and uses it as a tool to explore the consequences of several assumptions about the existence of prg. It is shown that if secure prg 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 K complexity of sets in P.