All reports by Author Alexander Shekhovtsov:

__
TR23-201
| 16th October 2023
__

Alexander Shekhovtsov, Georgii Zakharov#### Enumerating Complexity Revisited

Alexander Shekhovtsov, Georgii Zakharov

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.

... more >>>