S. Kautz and Per Bro Miltersen, Relative to a Random Oracle, NP is not Small (March 1, 1994).
Resource-bounded measure as originated by Lutz is an extension of classical measure theory which provides a probabilistic means of describing the relative sizes of complexity classes. Lutz has proposed the hypothesis that NP does not have measure zero in the class E2 = DTIME (2polynomial), 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 in this paper that relative to a random oracle, NP does not have measure zero in E2, improving the earlier result of Bennett and Gill 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 A0 is chosen by means of a bounded Kolmogorov-Loveland place selection, then the sequence A1 of unselected bits is random relative to A0, i.e., A0 and A1 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.
<%@ include file="cited.html" %>S.M. Kautz and P.B. Miltersen, "Relative to a Random Oracle, NP Is Not Small", Journal of Computer and System Sciences 53(2), pp. 235-250 (1996)
<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>