Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Andrej Muchnik:

TR04-054 | 5th June 2004
Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin

Non-reducible descriptions for conditional Kolmogorov complexity

Let a program p on input a output b. We are looking for a
shorter program p' having the same property (p'(a)=b). In
addition, we want p' to be simple conditional to p (this
means that the conditional Kolmogorov complexity K(p'|p) is
negligible). In the present paper, we prove that ... more >>>

TR04-015 | 24th February 2004
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

Enumerations of the Kolmogorov Function

A recursive enumerator for a function $h$ is an algorithm $f$ which
enumerates for an input $x$ finitely many elements including $h(x)$.
$f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$
is among the first $k(n)$ elements enumerated by $f$.
If there is a $k(n)$-enumerator for ... more >>>

TR01-089 | 29th October 2001
Andrej Muchnik, Nikolay Vereshchagin

Logical operations and Kolmogorov complexity. II

We invistigate what is the minimal length of
a program mapping A to B and at the same time
mapping C to D (where A,B,C,D are binary strings). We prove that
it cannot be expressed
in terms of Kolmogorv complexity of A,B,C,D, their pairs (A,B), (A,C),
..., their ... more >>>

TR00-015 | 16th February 2000
Andrej Muchnik, Alexej Semenov

Multi-conditional Descriptions and Codes in Kolmogorov Complexity

ISSN 1433-8092 | Imprint