Thumbnail Image
Publication

Limitations of Efficient Reducibility to the Kolmogorov Random Strings

Hitchcock, John
Abstract
Description
We show the following results for polynomial-time reducibility to RC, the set of Kolmogorov random strings.
Date
2012-05-24
Journal Title
Journal ISSN
Volume Title
Publisher
University of Wyoming. Libraries
Files
Thumbnail Image
Published
Adobe PDF, 174.02 KB
Research Projects
Organizational Units
Journal Issue
Keywords
kolmogorov random strings,polynominal-time reducibility,Turing reduction,universal machine,Engineering
Citation
URI
https://wyoscholar.uwyo.edu/handle/internal/1485
 https://doi.org/10.15786/wyoscholar/9619
Embedded videos
Collections
Faculty Publications | Computer Science
Show all metadata