2003/01/16 by S. M. Kautz, Steven M. Kautz, Kautz, S. M. · 1 citation
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/0301013
20 pages
arxiv created 2003/01/16 · openalex publication_date 2003/01/16 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, A0 is selected from A via a bounded Kolmogorov-Loveland selection rule, and A1 denotes the sequence of nonselected bits of A, then A1 is independent of A0; that is, A1 is algorithmically random relative to A0. 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.