1/1

3 files

Limitations of Efficient Reducibility to the Kolmogorov Random Strings

journal contribution

posted on 2012-05-24, 00:00 authored by John Hitchcock

We show the following results for polynomial-time reducibility to RC, the set of Kolmogorov random strings.

History

ISO

eng

Language

English

Publisher

University of Wyoming. Libraries

Journal title

Computability

Collection

Faculty Publications - Computer Science

Usage metrics

Categories

Applied Computer Science

Keywords

kolmogorov random strings polynominal-time reducibility Turing reduction universal machine Engineering

Licence

Exports