Coarse reducibility and algorithmic randomness
From MaRDI portal
Publication:2976378
Abstract: A coarse description of a subset A of omega is a subset D of omega such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1-random and B is computable from every coarse description D of A, then B is K-trivial, which implies that if A is in fact weakly 2-random then B is computable. Our main tool is a kind of compactness theorem for cone-avoiding descriptions, which also allows us to prove the same result for 1-genericity in place of weak 2-randomness. In the other direction, we show that if A is a 1-random set which Turing-reduces to 0', then there is a noncomputable c.e. set computable from every coarse description of A, but that not all K-trivial sets are computable from every coarse description of some 1-random set. We study both uniform and nonuniform notions of coarse reducibility. A set Y is uniformly coarsely reducible to X if there is a Turing functional Phi such that if D is a coarse description of X, then Phi^D is a coarse description of Y. A set B is nonuniformly coarsely reducible to A if every coarse description of A computes a coarse description of B. We show that a certain natural embedding of the Turing degrees into the coarse degrees (both uniform and nonuniform) is not surjective. We also show that if two sets are mutually weakly 3-random, then their coarse degrees form a minimal pair, in both the uniform and nonuniform cases, but that the same is not true of every pair of relatively 2-random sets, at least in the nonuniform coarse degrees.
Recommendations
Cites work
- A fixed-point-free minimal degree
- ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
- Algorithmic randomness and complexity.
- An inequality related to the isoperimetric inequality
- Asymptotic density, immunity and randomness
- Characterizing the strongly jump-traceable sets via randomness
- Computuing \(K\)-trivial sets by incomplete random sets
- Generic computability, Turing degrees, and asymptotic density
- Generic-case complexity, decision problems in group theory, and random walks.
- Lowness for genericity
- Splitting properties and jump classes
- Using random sets as oracles
Cited in
(18)- Strong Medvedev reducibilities and the KL-randomness problem
- Asymptotic density, computable traceability, and 1-randomness
- Robustness of average-case meta-complexity via pseudorandomness
- Some Questions in Computable Mathematics
- Computing from projections of random points
- Effective Brenier Theorem
- THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY
- Notions of robust information coding
- A minimal pair in the generic degrees
- Lowness, Randomness, and Computable Analysis
- Coherence of reducibilities with randomness notions
- Proofs of randomized algorithms in Coq
- scientific article; zbMATH DE number 1834658 (Why is no real title available?)
- Asymptotic density and the theory of computability: a partial survey
- Density-1-bounding and quasiminimality in the generic degrees
- Asymptotic density and computability
- Random Oracle Reducibility
- Proofs of Randomized Algorithms in Coq
This page was built for publication: Coarse reducibility and algorithmic randomness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976378)
