Independence Properties of Algorithmically Random Sequences
Kautz, S. M.
Original · EN
A bounded Kolmogorov-Loveland selection rule is an adaptive strategy for recursively selecting a subsequence of an infinite binary sequence; such a subsequence may be interpreted as the query sequence of a time-bounded Turing machine. In this paper we show that if A is an algorithmically random sequence, A₀ is selected from A via a bounded Kolmogorov-Loveland selection rule, and A₁ denotes the sequence of nonselected bits of A, then A₁ is independent of A₀; that is, A₁ is algorithmically random relative to A₀. This result has been used by Kautz and Miltersen [1] to show that relative to a random oracle, NP does not have p-measure zero (in the sense of Lutz [2]). [1] S. M. Kautz and P. B. Miltersen. Relative to a random oracle, NP is not small. Journal of Computer and System Sciences, 53:235-250, 1996. [2] J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220-258, 1992.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.