Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-201 | 16th October 2023 22:49

Enumerating Complexity Revisited


Authors: Alexander Shekhovtsov, Georgii Zakharov
Publication: 10th December 2023 09:44
Downloads: 126


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