Name
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 Kohnogorov complexity: For every underlying universal machine U. there is a constant a such that C is k(n)-enumerable only if k (it) >= 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 at e 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 V 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 S' introduced 2 by Canetti and independently Russell and Sundaram and the classes PSPACE. EXP. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.2178/jsl/1146620156 | JOURNAL OF SYMBOLIC LOGIC |
DocType | Volume | Issue |
Journal | 71 | 2 |
ISSN | Citations | PageRank |
0022-4812 | 6 | 0.81 |
References | Authors | |
17 | 9 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard Beigel | 1 | 247 | 28.41 |
| Harry Buhrman | 2 | 1607 | 117.99 |
| Peter A. Fejer | 3 | 34 | 6.80 |
| Lance Fortnow | 4 | 2788 | 352.32 |
| Piotr Grabowski | 5 | 43 | 5.61 |
| Luc Longpré | 6 | 245 | 30.26 |
| Andrei A. Muchnik | 7 | 70 | 9.33 |
| Frank Stephan | 8 | 313 | 28.88 |
| Leen Torenvliet | 9 | 290 | 41.73 |