 |
 |
 |
Freer, Cameron E. and Kjos-Hanssen, Bjoern - Randomness extraction and asymptotic Hamming distance
lmcs:889 - Logical Methods in Computer Science, September 25, 2013, Volume 9, Issue 3Randomness extraction and asymptotic Hamming distance
Authors: Freer, Cameron E. and Kjos-Hanssen, Bjoern
We obtain a non-implication result in the Medvedev degrees by studying sequences that are close to Martin-L\"of random in asymptotic Hamming distance. Our result is that the class of stochastically bi-immune sets is not Medvedev reducible to the class of sets having complex packing dimension 1.
Source : oai:arXiv.org:1008.0821
DOI : 10.2168/LMCS-9(3:27)2013
Volume: Volume 9, Issue 3
Published on: September 25, 2013
Submitted on: December 12, 2012
Keywords: Mathematics - Logic,Computer Science - Computational Complexity,Computer Science - Information Theory,Computer Science - Logic in Computer Science
Share
Consultation statistics
This page has been seen 72 times.
This article's PDF has been downloaded 94 times.