Relative to a random oracle, NP is not small

The resource-bounded measure (J. Lutz, 1992) is an extension of classical measure theory which provides a probabilistic means of describing the relative sizes of complexity classes. Lutz proposed the hypothesis that NP does not have measure zero in the class E₂=DTIME(2^polynomial), meaning loosely that NP contains a non-negligible subset of exponential time. This hypothesis implies 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≠NP. It is shown that relative to a random oracle, NP does not have measure zero in E₂, improving the result of Bennett and Gill (1981) that P≠NP relative to a random oracle. Several new techniques are introduced; in particular the proof exploits the independence properties of algorithmically random sequences, and a strong independence result is shown: if A is an algorithmically random sequence and a subsequence A₀ is chosen by means of a bounded Kolmogorov-Loveland place selection, then the sequence A₁ of unselected bits is random relative to A₀, i.e. A₀ and A₁ are independent. A bounded Kolmogorov-Loveland place selection is a very general type of recursive selection rule which may be interpreted as the sequence of oracle queries of a time-bounded Turing machine, so the methods used may be applicable to other questions involving random oracles