Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ALEXANDER SHEKHOVTSOV:
All reports by Author Alexander Shekhovtsov:

TR23-201 | 16th October 2023
Alexander Shekhovtsov, Georgii Zakharov

Enumerating Complexity Revisited

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 >>>



ISSN 1433-8092 | Imprint