# «Theory Comput Syst (2011) 49:227–245 DOI 10.1007/s00224-011-9321-z Variations on Muchnik’s Conditional Complexity Theorem Daniil Musatov · ...»

Theory Comput Syst (2011) 49:227–245

DOI 10.1007/s00224-011-9321-z

Variations on Muchnik’s Conditional Complexity

Theorem

Daniil Musatov · Andrei Romashchenko ·

Alexander Shen

Published online: 29 March 2011

© Springer Science+Business Media, LLC 2011

**Abstract**

Muchnik’s theorem about simple conditional descriptions states that for all

strings a and b there exists a program p transforming a to b that has the least possible length and is simple conditional on b. In this paper we present two new proofs of this theorem. The ﬁrst one is based on the on-line matching algorithm for bipartite graphs. The second one, based on extractors, can be generalized to prove a version of Muchnik’s theorem for space-bounded Kolmogorov complexity. Another version of Muchnik’s theorem is proven for a resource-bounded variant of Kolmogorov complexity based on Arthur–Merlin protocols.

Keywords Kolmogorov complexity · Extractors · On-line matching 1 Muchnik’s Theorem In this section we recall a result about conditional Kolmogorov complexity due to An. Muchnik [1]. By C(u) we denote Kolmogorov complexity of string u, i.e., the length of a shortest program generating u. The conditional complexity of u given v, the length of a shortest program that translates v to u, is denoted by C(u | v), see [2].

This study was supported by ANR Sycomore, NAFIT ANR-08-EMER-008-01 and RFBR 09-01-00709-a grants.

A. Romashchenko and A. Shen on leave from IITP RAS, Moscow, Russia.

D. Musatov Lomonosov Moscow State University, Moscow, Russia e-mail: musatych@gmail.com A. Romashchenko ( ) · A. Shen LIF Marseille, CNRS & Univ. Aix–Marseille, Marseille, France e-mail: andrei.romashchenko@gmail.com A. Shen e-mail: alexander.shen@lif.univ-mrs.fr 228 Theory Comput Syst (2011) 49:227–245 Theorem 1 Let a and b be two binary strings, C(a) n and C(a | b) k. Then there exists a string p such that

• C(a | p, b) ≤ O(log n);

• C(p) ≤ k + O(log n);

• C(p | a) ≤ O(log n).

This is true for all a, b, n, k, and the constants hidden in O(log n) do not depend on them.

** Remarks 1. In the second inequality we can replace complexity C(p) of a string p by its length |p|.**

Indeed, we can use the shortest description of p instead of p.

2. We may let k = C(a | b) + 1 and replace k + O(log n) by C(a | b) + O(log n) in the second inequality. We may also let n = C(a) + 1.

3. Finally, having |p| ≤ C(a | b) + O(log n), we can delete O(log n) last bits in p, and the ﬁrst and third inequalities will remain true. We come to the following reformulation of Muchnik’s theorem: for every two binary strings a and b there exist a binary string p of length at most C(a | b) such that C(a | p, b) ≤ O(log C(a)) and C(p | a) ≤ O(log C(a)).

Informally, Muchnik’s theorem says that there exists a program p that transforms b to a, has the minimal possible complexity C(a | b) up to a logarithmic term, and, moreover, can be easily obtained from a. The last requirement is crucial, otherwise the statement becomes a trivial reformulation of the deﬁnition of conditional Kolmogorov complexity.

This theorem is an algorithmic counterpart of Slepian–Wolf theorem [3] in multisource information theory. Assume that some person S knows b and wants to know a.

We know a and want to send some message p to S that will allow S to reconstruct a.

How long should be this message? Do we need to know b to be able to ﬁnd such a message? Muchnik’s theorem provides kind of a negative answer to the last question, though we still need a logarithmic advice. Indeed, the absolute minimum for a complexity of a piece of information p that together with b allows S to reconstruct a, is C(a | b). It is easy to see that this minimum can be achieved with logarithmic precision by a string p that has logarithmic complexity conditional on a and b. But it turns out that in fact b is not needed and we can provide p that is simple conditional on a and still does the job.

In many cases statements about Kolmogorov complexity have combinatorial counterparts, and sometimes it is easy to show the equivalence between complexity and combinatorial statements. In the present paper we study two different combinatorial objects closely related to Muchnik’s theorem and its proof.

First, in Sect. 2, we deﬁne the on-line matching problem for bipartite graphs. We

**formulate some combinatorial statement about on-line matchings. This statement:**

(1) easily implies Muchnik’s theorem and (2) can be proven using the same ideas that were used by Muchnik in his original proof, with some adjustments.

Second, in Sect. 3, following [4], we use extractors and their combinatorial properties. Based on this technique, we give a new proof of Muchnik’s theorem. With this method we prove versions of this theorem for polynomial space Kolmogorov Theory Comput Syst (2011) 49:227–245 229 complexity and also for some very special version of polynomial time Kolmogorov complexity.

This work was presented on the CSR2009 conference in Novosibirsk, Russia on 18–23 August, 2009, and the conference version of the paper was published in CSR2009 Proceedings by Springer-Verlag. This version of the paper is slightly rearranged and extended.

**2 Muchnik’s Theorem and On-line Matchings**

In this section we introduce a combinatorial problem that we call on-line matching. It can be considered as an on-line version of the classical matching problem. Then we formulate some combinatorial statement about on-line matchings and explain how it implies Muchnik’s theorem. Finally, we provide a proof of this combinatorial statement, starting with the off-line version of it. This ﬁnishes the proof of Muchnik’s theorem.

**2.1 On-line Matchings**

Consider a bipartite graph with the left part L, the right part R and a set of edges E ⊂ L × R. Let s be some integer. We are interested in the following property of the

**graph:**

for any subset L of L of size at most s there exists a subset E ⊂ E that performs a bijection between L and some R ⊂ R.

A necessary and sufﬁcient condition for this property is provided by well-known Hall’s theorem. It says that for each set L ⊂ L of size t ≤ s the set of all neighbors of elements of L contains at least t elements.

This condition is not sufﬁcient for the following on-line version of matching. We assume that an adversary gives us elements of L one by one, up to s elements. At each step we should provide a counterpart for each given element x, i.e., to choose some neighbor y ∈ R not used before. This choice is ﬁnal and cannot be changed later.

Providing a matching on-line, when next steps of the adversary are not known in advance, is a more subtle problem than the usual off-line matching. Now Hall’s criterion, while still being necessary, is no more sufﬁcient. For example, for the graph shown in the picture, one can ﬁnd a matching for each subset of size at most 2 of the left part, but this cannot be done on-line. Indeed, we are blocked if the adversary starts with x.

Now we formulate a combinatorial statement about on-line matching; then in Sect. 2.2 we show that this property implies Muchnik’s theorem, and in Sect. 2.3 we prove this property.

Combinatorial statement about on-line matchings (OM) There exists a constant c such that for every integers n and k, where k ≤ n, there exists a bipartite graph G whose left part L has size 2n, right part R has size 2k nc, each vertex in L has at most nc neighbors in R, and for which on-line matching is possible up to size 2k.

230 Theory Comput Syst (2011) 49:227–245 Note that the size of the on-line matching is close to the size of R up to a polynomial factor, and the degrees of all L-elements are polynomially bounded, so we are close to Hall’s bound.

2.2 Proof of Muchnik’s theorem First we show how (OM) implies Muchnik’s theorem. We may assume without loss of generality that the length of the string a (instead of its complexity) is less than n.

Indeed, if we replace a by a shortest program that generates a, all complexities involving a change by only O(log n) term: knowing the shortest program for a, we can get a without any additional information, and to get a shortest program for a given a we need only to know the value of C(a), because we can try all programs of length C(a) until one of them produces a. There may exist several different shortest programs for a; we take that one which appears ﬁrst when trying in parallel all programs of length C(a). As we have said, for similar reasons it does not matter whether we speak about C(p) or |p| in the conclusion of the theorem. We used C(p) to make the statement more uniform; however, in the proof we get the bound for |p| directly.

We may assume that n ≥ k, otherwise the statement of Theorem 1 is trivial (let p = a). Consider the graph G provided by (OM) with parameters n and k. Its left part L is interpreted as the set of all strings of length less than n; therefore, a is an element of L. Knowing b, we can enumerate all strings x of length less than n such that C(x | b) k. There exist at most 2k such strings, and a is one of them. The property (OM) implies that it is possible to ﬁnd an on-line matching for all these strings, in the order they appear during the enumeration. Let p be an element of R that corresponds to a in this matching.

Let us check that p satisﬁes all the conditions of Muchnik’s theorem. First of all, note that the graph G can be chosen in such a way that its complexity is O(log n).

Indeed, (OM) guarantees that a graph with the required properties exists. Given n and k, we can perform an exhaustive search until the ﬁrst graph with these properties is found. This graph is a computable function of n and k, so its complexity does not exceed the complexity of the pair (n, k), which is O(log n).

If a is given (as well as n and k), then p can be speciﬁed by its ordinal number in the list of a-neighbors. This list contains at most nc elements, so the ordinal number contains O(log n) bits.

To specify p without knowing a, we give the ordinal number of p in R, which is k + O(log n) bits long. Here we again need n and k, but this is another O(log n) bits.

To reconstruct a from b and p, we enumerate all strings of lengths less than n that have conditional complexity (relative to b, which is known) less than k, and ﬁnd R-counterparts for them using (OM) until p appears. Then a is the L-counterpart of p in this matching.

Formally speaking, for given n and k we should ﬁx not only a graph G but also some on-line matching procedure, and use the same procedure both for constructing p and for reconstructing a from b and p.

2.3 On-line Matchings Exist

First, let us prove a weaker statement when on-line matchings are replaced by offline matchings. In this case the statement can be reformulated using Hall’s criterion,

**and we get the following statement:**

Off-line version of (OM) There exists a constant c such that for any integers n and k, where n 1 and k ≤ n, there exists a bipartite graph G whose left part L is of size 2n, the right part R is of size 2k nc, each vertex in L has at most nc neighbors in R and for any subset X ⊂ L of size t ≤ 2k the set N (X) of all neighbors of all elements of X contains at least t elements.

are used; this is the only reason for rejection. So we get the contradiction with the condition #N(X) ≥ #X if X is the set of rejected elements.

Now we need to deal with rejected elements. They are forwarded to the “next layer” where the new task is to ﬁnd on-line matching for 2k−1 elements. If we can do this, then we combine both graphs using the same L and disjoint right parts R1 and

**R2 ; the elements rejected at the ﬁrst layer are sent to the second one. In other terms:**

(n, k) on-line problem is reduced to (n, k) off-line problem and (n, k − 1) on-line problem. The latter can then be reduced to (n, k − 1) off-line and (n, k − 2) on-line problems etc.

Finally we get k levels. At each level we serve at least half of the requests and forward the remaining ones to the next layer. After k levels of ﬁltering only one request can be left unserved, so one more layer is enough. Note also that we may use copies of the same graph on all layers.

More precisely, we have proven the following statement: Let G be a bipartite graph with left side L and right side R that satisﬁes the conditions of the off-line version for given n and k. Replace each element in R by (k + 1) copies, all connected to the same elements of L as before. Then the new graph provides on-line matchings up to size 2k.

Note that this construction multiplies both the size of R and the degree of vertices in L by (k + 1), which is a polynomial in n factor. The statement (OM) is proven.

**3 Muchnik’s Theorem and Extractors**

In this section we present another proof of Muchnik’s theorem based on the notion of extractors. This technique was ﬁrst used in a similar situation in [4]. With this technique we prove some versions of Muchnik’s theorem for resource-bounded Kolmogorov complexity. This result was presented in the Master Thesis of one of the authors [5].

3.1 Extractors Let G be a bipartite graph with N vertices in the left part and M vertices in the right part. The graph may have multiple edges. Let all vertices of the left part have the same degree D. Let us ﬁx an integer K 0 and a real number ε 0.

Deﬁnition 1 A bipartite graph G is a (K, ε)-extractor if for all subsets S of its left part such that #S ≥ K and for all subsets Y of the right part the inequality

holds, where E(S, Y ) stands for the set of edges between S and Y.