๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An Excursion to the Kolmogorov Random Strings

โœ Scribed by Harry Buhrman; Elvira Mayordomo

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
809 KB
Volume
54
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

We study the sets of resource-bounded Kolmogorov random strings:

. We show that the class of sets that Turing reduce to R t has measure 0 in EXP with respect to the resource-bounded measure introduced by Lutz. From this we conclude that R t is not Turing-complete for EXP. This contrasts with the resource-unbounded setting. There R is Turing-complete for co-RE. We show that the class of sets to which R t bounded truth-table reduces, has p 2 -measure 0 (therefore, measure 0 in EXP). This answers an open question of Lutz, giving a natural example of a language that is not weakly complete for EXP and that reduces to a measure 0 class in EXP. It follows that the sets that are p btt -hard for EXP have p 2 -measure 0.

๐Ÿ“œ SIMILAR VOLUMES

The length of an excursion above a linea
The length of an excursion above a linear boundary by a random walk
โœ Travis Lee; Max Minzner; Evan Fisher ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 249 KB

We consider random walks with steps that are independent and identically distributed with finite mean. The distribution and expected value of the length of an excursion that begins with the first step is investigated.

An improved algorithm for solving the ba
An improved algorithm for solving the banded cyclic string-to-string correction problem
โœ Chung Kuo-Liang ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 339 KB

The banded cyclic string-to-string correction (BCSSC) problem is a generalized version of the cyclic string-to-string correction (CSSC) problem, and has some applications in stereo matching and speech recognition. This note presents an improved algorithm for solving the BCSSC problem and the time co

An Elementary Approach to the Daniell-Ko
An Elementary Approach to the Daniell-Kolmogorov Theorem and Some Related Results
โœ Olav Kallenberg ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 799 KB

We give a short elementary proof of the DAMELL-KOLXOGOROV existence theorem for probability measures on product spaces, assuming nothing but the existence of LEBESGUE mensure on the unit interval. Related approaches are used to prove the existence of regular conditional distributions directly on Pol