Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > THE A PRIORI PROBABILITY:
Reports tagged with the a priori probability:
TR04-030 | 9th March 2004
Nikolay Vereshchagin

Kolmogorov complexity of enumerating finite sets

Solovay has proven that
the minimal length of a program enumerating a set A
is upper bounded by 3 times the absolute value of the
logarithm of the
probability that a random program will enumerate A.
It is unknown whether one can replace the constant
3 by a smaller constant.
more >>>


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