FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

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

-- [ Page 1 ] --

Theory Comput Syst (2011) 49:227–245

DOI 10.1007/s00224-011-9321-z

Variations on Muchnik’s Conditional Complexity


Daniil Musatov · Andrei Romashchenko ·

Alexander Shen

Published online: 29 March 2011

© Springer Science+Business Media, LLC 2011


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 first 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 first 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 definition 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 find 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 define 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 finishes 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


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 sufficient 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 sufficient 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 final 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 sufficient. For example, for the graph shown in the picture, one can find 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 first 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 find 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 satisfies 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 first 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 specified 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 find 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 fix 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 find 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 first 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 filtering 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 satisfies 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 first 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 fix an integer K 0 and a real number ε 0.

Definition 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.

Pages:   || 2 | 3 |

Similar works:

«Sociological Practice Volume 7 Issue 1 The Development of Clinical and Applied Article 16 Sociology January 1989 Changing the Definition of the Situation: Toward a Theory of Sociological Intervention Roger A. Straus Follow this and additional works at: http://digitalcommons.wayne.edu/socprac Part of the Sociology Commons Recommended Citation Straus, Roger A. (1989) Changing the Definition of the Situation: Toward a Theory of Sociological Intervention, Sociological Practice: Vol. 7: Iss. 1,...»

«Tuesday of the Other June by Norma Fox Mazer Be good, be good, be good, be good, my Junie, my mother sang as she combed my hair; a song, a story, a croon, a plea. It's just you and me, two women alone in the world, June darling of my heart; we have enough troubles getting by, we surely don't need a single one more, so you keep your sweet self out of fighting and all that bad stuff. People can be little-hearted, but turn the other cheek, smile at the world, and the world'll surely smile back. We...»

«INFORME SANTIAGO DEL ESTERO Ministerio de Justicia, Seguridad y Derechos Humanos 1 Introducción En cumplimiento de la misión encomendada por el Sr. Ministro de Justicia, Seguridad y Derechos Humanos, Dr. Gustavo Béliz, los Secretarios de Justicia y Asuntos Penitenciarios, Dr. Pablo Lanusse y de Derechos Humanos Dr. Eduardo Luis Duhalde viajaron los días 10 al 12 de septiembre de 2003 a la provincia de Santiago del Estero. Este viaje estaba precedido por un intenso trabajo de seguimiento y...»

«Surviving Christmas and New Year Staying safe and keeping well 2013 Edition 1 Why we wrote this booklet Sometimes people find that the Christmas and New Year period is really hard. Everyone else seems to be having a great time but you’re feeling worried or find it hard to cope. And it’s worse when you have problems with drugs or alcohol, because you are trying to keep yourself well when other people are drinking and having parties. And all the places where you get support at other times of...»

«Six senses Spa Yao Noi SPA MENU Welcome to Six Senses Yao Noi Spa At Six Senses Yao Noi Spa, we aim to help people reconnect with themselves, others and the world around them. Highly skilled Six Senses Spa therapists use a synergy of natural products to provide a comprehensive range of award-winning signature treatments plus rejuvenation and wellness specialties of the region. We are committed to delivering integrated wellness experiences, and providing guidance and inspiration to allow our...»

«Extracting Team Mental Models Through Textual Analysis Kathleen M. Carley Associate Professor of Sociology Department of Social and Decision Sciences Carnegie Mellon University May 1997 The final version of this paper appears in: Kathleen M. Carley, 1997, “Extracting Team Mental Models Through Textual Analysis.” Journal of Organizational Behavior, 18: 533-538. This work was supported in part by the NSF under grant IRI-9216760. Many thanks to Sara Kiesler and Doug Wholey for their...»

«JOHN MICHAEL RILEY Curriculum Vitae   July 2015 MAILING  ADDRESS:         TELEPHONE:     (662)  325-­‐7986   CONTACT  INFORMATION   P.O.  Box  5187           CELL:       (662)  617-­‐5711   Mississippi  State,  MS    39762                     WORK  EMAIL:     jmr26@msstate.edu   PHYSICAL  ADDRESS:         PERSONAL  EMAIL:   jmriley79@gmail.com   255  Tracey  Drive...»

«THE PROBLEM OF IDENTİTY, THE SEARCH FOR THE SELF-CONSCİOUSNESS AND THE REFLECTİONS OF HEGELİAN PHİLOSOPHY ON RAZUMOV İN CONRAD’S UNDER WESTERN EYES Yiğit SÜMBÜL* Abstract: The aim of this article is to display the problem of identity and the search for self-consciousness, in Hegelian terms, intensively experienced by Razumov in Under Western Eyes by the famous Polish-born English novelist Joseph Conrad. In the novel, written in the light of Conrad‟s own experiences in the past, the...»


«Based upon the book by William Steig Story by Andrew Adamson Screenplay by Peter Seaman & Jeffrey Price and Chris Miller & Aron Warner Shrek the Third Final Screening Script 1.INT. MEDIEVAL TIMES THEATER NIGHT A familiar beam of light shines down. The beam of light descends onto a stage. Lightning flashes to reveal Prince Charming riding his valiant steed Chauncey across the open plains. The wind blows back his golden mane. PRINCE CHARMING Onward Chauncey, to the highest room of the tallest...»

«Inter-firm cooperation in high-tech industries A study of R&D partnerships in pharmaceutical biotechnology Inter-firm cooperation in high-tech industries: a study of R&D partnerships in pharmaceutical biotechnology c A.H.W.M. Roijakkers, Maastricht 2003 Proefschrift Universiteit Maastricht ISBN 90-5278-374-8 Opmaak in LTEX: Johan Willekens, Echt A Omslagontwerp: Jos van den Einde, Oosterhout Druk: Datawyse/Universitaire Pers Maastricht Inter-firm cooperation in high-tech industries A study of...»

«Skill Reading Comprehension Name_ South Korea Stories about the country and culture of Korea.SUMMARY: Each story delves into the country of Korea, discussing the food, culture, and things to see in Korea. Part entertainment and part social studies, these stories should enlighten and delight as students learn more about the interesting and important country.TABLE OF CONTENTS: Visiting Korea Korean New Year Kimbap Korean BBQ The Princess Disease What is Kimchi? The Old Castle Hangul Harvest...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.