16 citations · 18 across the 4 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2017
On low for speed oracles
Laurent Bienvenu, Rod Downey
Relativizing computations of Turing machines to an oracle is a central concept in the theory of computation, both in complexity theory and in computability theory(!). Inspired by l…
cs.CC2009★ 16 cited
Kolmogorov Complexity and Solovay Functions
Laurent Bienvenu, Rod Downey
Solovay proved that there exists a computable upper bound f of the prefix-free Kolmogorov complexity function K such that f (x) = K(x) for infinitely many x. In this paper, we cons…