Please use this identifier to cite or link to this item:

`https://doi.org/10.2178/jsl/1146620156`

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. https://doi.org/10.2178/jsl/1146620156 |

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 |

URI: | http://scholarbank.nus.edu.sg/handle/10635/103202 |

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.

#### SCOPUS^{TM}

Citations

14
checked on Apr 2, 2020

#### WEB OF SCIENCE^{TM}

Citations

14
checked on Mar 17, 2020

#### Page view(s)

72
checked on Mar 28, 2020

#### Google Scholar^{TM}

Check
#### Altmetric

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