 |
 |
Cameron E. Freer ; Bjoern Kjos-Hanssen - Randomness extraction and asymptotic Hamming distance
lmcs:889 - Logical Methods in Computer Science, September 25, 2013, Volume 9, Issue 3 - https://doi.org/10.2168/LMCS-9(3:27)2013Randomness extraction and asymptotic Hamming distance
Authors: Cameron E. Freer ; Bjoern Kjos-Hanssen
We obtain a non-implication result in the Medvedev degrees by studying sequences that are close to Martin-Löf 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
Volume: Volume 9, Issue 3
Published on: September 25, 2013
Accepted on: June 25, 2015
Submitted on: December 12, 2012
Keywords: Mathematics - Logic,Computer Science - Computational Complexity,Computer Science - Information Theory,Computer Science - Logic in Computer Science
Consultation statistics
This page has been seen 1444 times.
This article's PDF has been downloaded 245 times.