39 citations · 89 across the 17 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.CC2014
Computational Complexity of Functions
Leonid A. Levin
Below is a translation from my Russian paper. I added references, unavailable to me in Moscow. Similar results have been also given in [Schnorr Stumpf 75] (see also [Lynch 75]). Ea…
cs.CC2014★ 1 cited
Occam Bound on Lowest Complexity of Elements
Leonid A. Levin
The combined universal probability M(D) of strings x in sets D is close to max_{x \in D} M({x}): their ~ logs differ by at most D's information j = I(D:H) about the halting sequenc…