Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-201 | 12th November 2026 23:23

Enumerating Complexity Revisited

RSS-Feed




Revision #1
Authors: Alexander Shekhovtsov, Georgii Zakharov
Accepted on: 12th November 2026 23:23
Downloads: 7
Keywords: 


Abstract:

We study the relation between deterministic and randomized enumerating Kolmogorov complexity of sets S ? ?. Let D(S) be the length of a shortest input on which a fixed optimal deterministic machine enumerates S, and let R(S) be the probability that a fixed optimal randomized machine enumerates S. It is easy to see that ?log R(S) ? D(S) + O(log D(S)) for every S; the converse direction is much harder. Solovay proved D(S) ? ?3 log R(S) + O(log log(1/R(S))) for all S, while for finite sets the sharper bound with the constant 2 is known.

We show that the case of infinite sets carries no extra cost: any inequality of the form D(F) ? ?? log R(F) + O(log log(1/R(F))) with a computable ?, valid for all finite F, automatically extends to all sets. More generally, we prove a single dichotomy from which such transfer results follow for an arbitrary computable non-decreasing bound, and which also shows that every c.e. set S has a finite subset F such that F has at least as large deterministic complexity as S but randomized one approximately the same or lower. Our result makes qualitative progress on a problem studied by Solovay in 1977 by showing that the search for the optimal constant can be reduced to a purely combinatorial question about a game played with finite sets. In particular, our result yields D(S) ? ?2 log R(S) + O(log log(1/R(S))) for every S, improving Solovay's constant 3 to 2.



Changes to previous version:

A little improvement of the exposition


Paper:

TR23-201 | 16th October 2023 22:49

Enumerating Complexity Revisited





TR23-201
Authors: Alexander Shekhovtsov, Georgii Zakharov
Publication: 10th December 2023 09:44
Downloads: 1086
Keywords: 


Abstract:

We reduce the best-known upper bound on the length of a program that enumerates a set in terms of the probability of it being enumerated by a random program. We prove a general result that any linear upper bound for finite sets implies the same linear bound for infinite sets.

So far, the best-known upper bound was given by Solovay. He showed that the minimum length of a program enumerating a subset $S$ of natural numbers is bounded by minus three binary logarithms of the probability that a random program will enumerate S. Later, Vereshchagin showed that the constant can be improved from three to two for finite sets. In this work, using the method proposed by Solovay, we demonstrate that any bound for finite sets implies the same for infinite sets, modulo logarithmic factors. Using Vereshchagin's result, we improve the current best-known upper bound from three to two.



ISSN 1433-8092 | Imprint