Loading...
Thumbnail Image
Item

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
Research Projects
Organizational Units
Journal Issue
Keywords
kolmogorov random strings , polynominal-time reducibility , Turing reduction , universal machine , Engineering
Citation
Embedded videos