Enumerations of the Kolmogorov function.

*(English)*Zbl 1165.03025Summary: 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:

{\(\bullet\)} For every underlying universal machine \(U\), there is a constant \(a\) such that \(C\) is \(k(n)\)-enumerable only if \(k(n) \geq n/a\) for almost all \(n\).

{\(\bullet\)} 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.

{\(\bullet\)} There exists an r.e., Turing-incomplete set \(A\) such that 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\):

{\(\bullet\)} 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\).

{\(\bullet\)} 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 \(\text{S}_2^{\text{p}}\), introduced by Canetti and independently by Russell and Sundaram, and the classes PSPACE, EXP.

{\(\bullet\)} \(\text{S}_2^{\text{p}}\) is the class of all sets \(A\) for which there is a polynomially bounded function \(g\) such that there is a polynomial-time tt-reduction which reduces \(A\) to every strong 2-enumerator for \(g\).

{\(\bullet\)} PSPACE is the class of all sets \(A\) for which there is a polynomially bounded function \(g\) such that there is a polynomial-time Turing reduction which reduces \(A\) to every strong 2-enumerator for \(g\). Interestingly, \(g\) can be taken to be the Kolmogorov function for the conditional space-bounded Kolmogorov complexity.

{\(\bullet\)} EXP is the class of all sets \(A\) for which there is a polynomially bounded function \(g\) and a machine \(M\) which witnesses \(A \in \text{PSPACE}^f\) for all strong 2-enumerators \(f\) for \(g\).

Finally, we show that any strong \(O(\log n)\)-enumerator for the conditional space-bounded Kolmogorov function must be PSPACE-hard if \(\text{P}=\text{NP}\).

We determine exactly how hard it is to enumerate the Kolmogorov function, which assigns to each string \(x\) its Kolmogorov complexity:

{\(\bullet\)} For every underlying universal machine \(U\), there is a constant \(a\) such that \(C\) is \(k(n)\)-enumerable only if \(k(n) \geq n/a\) for almost all \(n\).

{\(\bullet\)} 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.

{\(\bullet\)} There exists an r.e., Turing-incomplete set \(A\) such that 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\):

{\(\bullet\)} 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\).

{\(\bullet\)} 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 \(\text{S}_2^{\text{p}}\), introduced by Canetti and independently by Russell and Sundaram, and the classes PSPACE, EXP.

{\(\bullet\)} \(\text{S}_2^{\text{p}}\) is the class of all sets \(A\) for which there is a polynomially bounded function \(g\) such that there is a polynomial-time tt-reduction which reduces \(A\) to every strong 2-enumerator for \(g\).

{\(\bullet\)} PSPACE is the class of all sets \(A\) for which there is a polynomially bounded function \(g\) such that there is a polynomial-time Turing reduction which reduces \(A\) to every strong 2-enumerator for \(g\). Interestingly, \(g\) can be taken to be the Kolmogorov function for the conditional space-bounded Kolmogorov complexity.

{\(\bullet\)} EXP is the class of all sets \(A\) for which there is a polynomially bounded function \(g\) and a machine \(M\) which witnesses \(A \in \text{PSPACE}^f\) for all strong 2-enumerators \(f\) for \(g\).

Finally, we show that any strong \(O(\log n)\)-enumerator for the conditional space-bounded Kolmogorov function must be PSPACE-hard if \(\text{P}=\text{NP}\).

##### MSC:

03D80 | Applications of computability and recursion theory |

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |

PDF
BibTeX
XML
Cite

\textit{R. Beigel} et al., J. Symb. Log. 71, No. 2, 501--528 (2006; Zbl 1165.03025)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Proceedings of the 13th Symposium on Theoretical Aspects of Computer Science 1046 pp 25– (1996) |

[2] | DOI: 10.1016/0020-0190(91)90103-O · Zbl 0733.68030 |

[3] | DOI: 10.1016/0890-5401(89)90063-1 · Zbl 0679.68072 |

[4] | DOI: 10.1137/S0097539799360148 · Zbl 0977.68046 |

[5] | DOI: 10.1006/inco.1993.1014 · Zbl 0781.68057 |

[6] | Electronic Colloquium on Computational Complexity (ECCC) (2004) |

[7] | Soviet Mathematics Doklady 9 pp 1251– (1968) |

[8] | DOI: 10.1070/RM1970v025n06ABEH001269 · Zbl 0222.02027 |

[9] | Proceedings of the 5th Annual Conference on Structure in Complexity Theory pp 232– (1990) |

[10] | Technical Report ILLC Technical Report ML 1990-05 (1990) |

[11] | Proceedings 15th IEEE Conference on Computational Complexity pp 44– (2000) |

[12] | Algorithmic randomness and lowness 66 pp 1199– (2001) |

[13] | Draft of a paper on Chaitin’s work pp 215– (1975) |

[14] | Problems of Information Transmission 1 pp 1– (1965) |

[15] | Transactions of the American Mathematical Society 173 pp 33– (1972) · Zbl 0247.00014 |

[16] | Transactions of the American Mathematical Society 275 pp 599– (1983) |

[17] | Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science pp 439– (1983) |

[18] | Models and computahility: Invited papers from Logic Colloquium 1997 – European Meeting of the Association for Symbolic Logic, Leeds, July 1997 pp 117– (1999) |

[19] | DOI: 10.1002/malq.19590050703 · Zbl 0108.00602 |

[20] | DOI: 10.1142/9789812705815_0005 |

[21] | DOI: 10.1016/0304-3975(76)90005-0 · Zbl 0328.02029 |

[22] | DOI: 10.1145/321356.321363 · Zbl 0158.25301 |

[23] | DOI: 10.1016/0020-0190(96)00016-6 · Zbl 0875.68425 |

[24] | DOI: 10.1016/S0019-9958(64)90131-7 · Zbl 0259.68038 |

[25] | DOI: 10.1002/malq.19940400209 · Zbl 0806.03027 |

[26] | DOI: 10.1145/146585.146609 · Zbl 0799.68096 |

[27] | DOI: 10.1007/s000370050007 · Zbl 0912.68054 |

[28] | Computational complexity (1994) · Zbl 0833.68049 |

[29] | DOI: 10.1016/j.aim.2004.10.006 · Zbl 1141.03017 |

[30] | DOI: 10.1145/146585.146605 · Zbl 0799.68097 |

[31] | An introduction to Kolmogorov complexity audits applications (1997) |

[32] | Lowness for the class of random sets pp 1396– (1999) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.