RELATIVE TO A RANDOM ORACLE, NP IS NOT SMALL

Resource-bounded measure as originated by Lutz is an extension of clas sical measure theory which provides a probabilistic means of describin g the relative sizes of complexity classes. Lutz has proposed the hypo thesis that NP does not have p-measure zero, meaning loosely that NP c ontains a non-negligible subset of exponential time. This hypothesis i mplies a strong separation of P from NP and is supported by a growing body of plausible consequences which are not known to follow from the weaker assertion P not equal NP. It is shown in this paper that relati ve to a random oracle, NP does not have p-measure zero. The proof expl oits the following independence property of algorithmically random seq uences: if A is an algorithmically random sequence and a subsequence A (0) is chosen by means of a bounded Kolmogorov-Loveland place selectio n, then the sequence A(1) of unselected bits is random relative to A(0 ) i.e., A(0) and A(1) are independent. A bounded Kolmogorov-Loveland p lace selection is a very general type of recursive selection rule whic h may be interpreted as the sequence of oracle queries of a time-bound ed Turing machine, so the methods used may be applicable to other ques tions involving random oracles. (C) 1996 Academic Press, Inc.