A.Muchnik, A.Shen, N.Vereshchagin, M.Vyugin. Non-reducible descriptions for conditional Kolmogorov complexity.
ECCC Report, TR04-054, Jun 29, 2004
See also: Theory and Applications of Models of Computation,
Lecture Notes in Computer Science, Springer Berlin/Heidelberg, 3959 (2006), p.308-317
(a talk given in Beijing conference, May 2006). MR2277252
Extended version: Andrej Muchnik, Alexander Shen, Mikhail Ustinov, Nikolai Vereshchagin, Michael Vyugin, Non-reducible descriptions for conditional Kolmogorov complexity.
Theoretical Computer Science, 2007, 384 (1), 77--86.
Download (186.2 KB)
| Authors: Shen A. |