Please use this identifier to cite or link to this item:
Title: Enumerations of the kolmogorov function
Authors: Beigel, R.
Buhrman, H.
Fejer, P.
Fortnow, L.
Grabowski, P.
Longpré, L.
Muchnik, A.
Stephan, F. 
Torenvliet, L.
Issue Date: Jun-2006
Citation: Beigel, R., Buhrman, H., Fejer, P., Fortnow, L., Grabowski, P., Longpré, L., Muchnik, A., Stephan, F., Torenvliet, L. (2006-06). Enumerations of the kolmogorov function. Journal of Symbolic Logic 71 (2) : 501-528. ScholarBank@NUS Repository.
Abstract: A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x),f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function. which assigns to each string x its Kolmogorov complexity: For every underlying universal machine U, there is a constant a such that C is k(n)-enumerable only if k(n) ≥ n/a for almost all n. For any given constant k, the Kolmogorov function is k-enumerable relative to an oracle A if and only if A is at least as hard as the halting problem. There exists an r.e., Turing-incomplete set A such for every non-decreasing and unbounded recursive function k. the Kolmogorov function is k(n)-enumerable relative to A. The last result is obtained by using a relativizable construction for a nonrecursive set A relative to which the prefix-free Kolmogorov complexity differs only by a constant from the unrelativized prefix-free Kolmogorov complexity. Although every 2-enumerator for C is Turing hard for K, we show that reductions must depend on the specific choice of the 2-enumerator and there is no bound on the quantity of their queries. We show our negative results even for strong 2-enumerators as an oracle where the querying machine for any x gets directly an explicit list of all hypotheses of the enumerator for this input. The limitations are very general and we show them for any recursively bounded function g: For every Turing reduction M and every non-recursive set B. there is a strong 2-enumerator f for g such that M does not Turing reduce B to f. For every non-recursive set B, there is a strong 2-enumerator f for g such that B is not wtt-reducible to f. Furthermore, we deal with the resource-bounded case and give characterizations for the class S2 P introduced by Canetti and independently Russell and Sundaram and the classes PSPACE, EXP. © 2006. Association for Symbolic Logic.
Source Title: Journal of Symbolic Logic
ISSN: 00224812
DOI: 10.2178/jsl/1146620156
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Apr 2, 2020


checked on Mar 17, 2020

Page view(s)

checked on Mar 28, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.