Limit complexities revisited [ once more ] - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2012

Limit complexities revisited [ once more ]


Revised version of "Limit complexities revisited" [The original version of this work [2] contained a weaker (and cumbersome) version of Conidis' result, and the proof used low basis theorem (in quite a strange way). The full version was formulated as a conjecture. This conjecture was later proved by Conidis. Bruno Bauwens (personal communication) noted that the proof can be obtained also by a simple modification of our original argument, and we reproduce Bauwens' argument with his permission.]
No file

Dates and versions

lirmm-00786224 , version 1 (08-02-2013)


  • HAL Id : lirmm-00786224 , version 1


Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin. Limit complexities revisited [ once more ]. arxiv:1204-0201, 2012, pp.1-12. ⟨lirmm-00786224⟩
157 View
0 Download


Gmail Mastodon Facebook X LinkedIn More