WWW.DISSERTATION.XLIBX.INFO FREE ELECTRONIC LIBRARY - Dissertations, online materials

<< HOME
CONTACTS

Pages:   || 2 | 3 |

# «The Journal of Symbolic Logic Volume 00, Number 0, XXX 0000 COMPLEXITY OF COMPLEXITY AND STRINGS WITH MAXIMAL PLAIN AND PREFIX KOLMOGOROV COMPLEXITY ...»

-- [ Page 1 ] --

The Journal of Symbolic Logic

Volume 00, Number 0, XXX 0000

## PLAIN AND PREFIX KOLMOGOROV COMPLEXITY

B. BAUWENS AND A. SHEN

Abstract. P´ter G´cs showed (G´cs 1974) that for every n there exists a bit string x of

e a a

length n whose plain complexity C (x) has almost maximal conditional complexity relative

to x, i.e., C (C (x)|x) ≥ log n − log(2) n − O(1). (Here log(2) i = log log i.) Following Elena Kalinina (Kalinina 2011), we provide a simple game-based proof of this result; modifying her argument, we get a better (and tight) bound log n − O(1). We also show the same bound for preﬁx-free complexity.

Robert Solovay showed (Solovay 1975) that inﬁnitely many strings x have maximal plain complexity but not maximal preﬁx complexity (among the strings of the same length): for some c there exist inﬁnitely many x such that |x| − C (x) ≤ c and |x| + K (|x|) − K (x) ≥ log(2) |x| − c log(3) |x|. In fact, the results of Solovay and G´cs are closely related. Using a the result above, we provide a short proof for Solovay’s result. We also generalize it by showing that for some c and for all n there are strings x of length n with n − C (x) ≤ c and n + K (n) − K (x) ≥ K (K (n)|n) − 3 K (K (K (n)|n)|n) − c.

We also prove a close upper bound K (K (n)|n) + O(1).

Finally, we provide a direct game proof for Joseph Miller’s generalization (Miller 2006) of the same Solovay’s theorem: if a co-enumerable set (a set with c.e. complement) contains for every length a string of this length, then it contains inﬁnitely many strings x such that (2) (3) |x| + K(|x|) − K(x) ≥ log |x| − O(log |x|).

Introduction. Plain Kolmogorov complexity C (x) of a binary string x was deﬁned in [6] as the minimal length of a program that computes x. (See, e.g., [4, 8, 12, 15] for more details.) It was clear from the beginning that this complexity function is not computable: no algorithm can compute C (x) given x. In [3] (see also [4, 8]) a stronger non-uniform version of this result was proven: for every n there exists a string x of length n such that conditional complexity C (C (x)|x), i.e., the minimal length of a program that maps x to C (x), is at Bruno Bauwens is supported by the Portuguese science foundation FCT CSI 2 (SFRH/BPD/75129/2010); and partially supported by (PTDC/EIACCO/099951/2008) and NAFIT ANR-08-EMER-008-01 projects. Alexander Shen is supported by NAFIT ANR-08-EMER-008-01 project. Part of this paper was published in the proceedings of the 39-th International Conference on Automata, Languages and Programming (ICALP2012). The authors are grateful to Elena Kalinina and Nikolay Vereshchagin for useful discussions.

–  –  –

least log n − log(2) n − O(1). (If the complexity function were computable, this conditional complexity would be bounded.) In Section 1 we revisit this classical result and improve it a bit by removing the log(2) n term.1 No further improvement is possible because C (x) ≤ n + O(1) for every string x of length n, therefore C (C (x)|x) ≤ log n + O(1) for all such x.

We also prove that we can guarantee C (x) ≥ n/2 (in addition to C (C (x)|x) ≥ log n − O(1)), which was (in weaker form) conjectured by Robert Solovay and Gregory Chaitin, and mentioned as Conjecture 3.14.6 on p. 145 in [2].

We use a game technique that was developed by Andrej Muchnik (see [11, 10, 14]) and turned out to be useful in many cases. Recently Elena Kalinina (in her master thesis [5]) used it to provide a proof of G´cs’ result. We use a more a detailed analysis of essentially the same game to get a better bound.

In Section 2 we use this improved bound to provide a simple proof of an old result due to Solovay. The complexity C (x) of an n-bit string x never exceeds n+O(1), and for most n-bit strings x the value of C (x) is close to n. Such strings may be called “C-random”. There is another version of complexity, called preﬁx complexity, where the programs are assumed to be self-delimiting (see [4, 8, 12] for details). For an n-bit string x its preﬁx complexity K (x) does not exceed n + K (n) + O(1), and for most n-bit strings x the value of K (x) is close to n + K (n). Such strings may be called K-random2.

A natural question arises: how “C-randomness” and “K-randomness” are related? This question was studied by Solovay who proved that K-randomness implies C-randomness but not vice versa (see the unpublished notes [13] and its exposition in [2]). More precisely, consider the “randomness deﬁciencies”

dC (x) = |x| − C (x) and dK (x) = |x| + K (|x|) − K (x). Solovay proved that:

1. dC (x) ≤ O(dK (x));

2. the reverse statement can be proved with additional error term:

dK (x) ≤ O(dC (x)) + log(2) n for every n-bit string x;

3. the error term cannot be deleted: there exists a constant c and inﬁnitely many strings x such that dC (x) ≤ c but dK (x) ≥ log(2) |x| − O(log(3) |x|).

Using the result of Section 1, we provide a short proof for statement (3), the most diﬃcult one, even in a stronger form where O(log(3) |x|) is replaced by O(1). Then we prove a stronger statement about strings of ﬁxed length n, with

close lower and upper bounds:

• dK (x) ≤ O(dC (x)) + K (K (n)|n) for every n-bit string x;

• for some constant c and for every n there exist a string x of length n such that dC (x) ≤ c and dK (x) ≥ K (K (n)|n) − 3 K (K (K (n)|n)|n) − c.

1 Note added in proof: alternatively, this improvement can also be shown using [1, Theorem 3.1] (and Theorem 5.1 for preﬁx complexity).

2 In [2], such strings are called “strongly K-random”, in contrast to the “weakly K-random” strings x, which only satisfy K (x) ≥ |x| − O(1).

## COMPLEXITY OF COMPLEXITY AND MAXIMAL C AND K - COMPLEXITY

It is stronger because the result of Section 1 then allows us to choose n in such a way that K (K (n)|n) = log(2) n + O(1); this choice also makes the other term O(1).

Finally, in Section 3 we give another example of game technique by presenting a simple proof of a diﬀerent generalization of Solovay’s result. This generalization is due to Miller [9]: every co-enumerable set (a set with c.e. complement) that contains a string of every length, contains inﬁnitely many x such that

–  –  –

§1. Complexity of complexity can be high.

Theorem 1. There exist some constant c such that for every n there exists a string x of length n such that C (C (x)|x) ≥ log n − c.

To prove this theorem, we ﬁrst deﬁne some game and show a winning strategy for the game. (The connection between the game and the statement that we want to prove will be explained later.)

1.1. The game. Game Gn has parameter n and is played on a rectangular board divided into cells. The board has 2n columns and n rows numbered 0, 1,..., n − 1 (the bottom row has number 0, the next one has number 1 and so on, the top row has number n − 1), see Fig. 1.

Initially the board is empty. Two players: White and Black, alternate their moves. At each move, a player can pass or place a token (of his color) on the board. The token can not be moved or removed afterwards. Also Black may blacken some cell instead. Let us agree that White starts the game (though it does not matter).

The position of the game should satisfy some restrictions; the player who violates these restrictions, loses the game immediately. Formally the game is inﬁnite, but since the number of (non-trivial) moves is a priori bounded, it can be considered as ﬁnite, and the winner is determined by the last (limit) position on the board.

Restrictions: (1) each player may put at most 2i tokens in row i (thus the total number of black and white tokens in a row can be at most 2i + 2i ); (2) in each column Black may blacken at most half of the cells.

We say that a white token is dead if either it is on a blackened cell or has a black token in the same column strictly below it.

Winning rule: Black wins if he killed all white tokens, i.e., if each white token is dead in the ﬁnal position.

–  –  –

For example, if the game ends in the position shown at Fig. 1, the restrictions are not violated (there are 3 ≤ 22 white tokens in row 2 and 1 ≤ 21 white token in row 1, as well as 1 ≤ 22 black token in row 2 and 1 ≤ 20 black token in row 0).

Black loses because the white token in the third column is not dead: it has no black token below and the cell is not blackened. (There is also one living token in the fourth column.)

1.2. How White can win. The strategy is quite simple. White starts by placing a white token in an upper row of some column and waits until Black kills it, i.e., blackens the cell or places a black token below. In the ﬁrst case White puts a token directly below it, and waits again. Since Black has no right to make all cells in a column black (at most half may be blackened), at some point he will be forced to place a black token below the white token in this column.

After that White switches to some other column. (The ordering of columns is not important; we may assume that White moves from left to right.) Note that when White switches to a next column, it may happen that there is a black token in this column or some cells are already blackened. If there is already a black token, White switches again to the next column; if some cell is blackened, White puts her token in the topmost white (non-blackened) cell.

This strategy allows White to win. Indeed, Black cannot place his tokens in all the columns due to the restrictions (the total number of his tokens is n−1 i n i=0 2 = 2 − 1, which is less than the number of columns). White also cannot violate the restriction for the number of her tokens on some row i: all dead tokens have a black token strictly below them, so the number of them on row i i−1 is at most j=0 2j = 2i − 1, hence White can put an additional token.

In fact we may even allow Black to blacken all the cells except one in each column, and White will still win, but this is not needed (and the n/2 restriction will be convenient later).

1.3. Proof of G´cs’ theorem. Let us show that for each n there exists a a string x of length n such that C (C (x|n)|x) ≥ log n−O(1). Note that here C (x|n) is used instead of C (x); the diﬀerence between these two numbers is O(log n) since n can be described by log n bits, so the diﬀerence between the complexities of these two numbers is O(log(2) n).

Consider the following strategy for Black (assuming that the columns of the

table are indexed by strings of length n):

• Black blackens the cell in column x and row i as soon as he discovers that C (i|x) log n − 1. (The constant 1 guarantees that less than half of the cells will be blackened.) Note that Kolmogorov complexity is an upper semicomputable function, and Black approximates it from above, so more and more cells are blackened.

• Black puts a black token in a cell (x, i) when he ﬁnds a program of length i that produces x with input n (this implies that C (x|n) ≤ i). Note that there are at most 2i programs of length i, so Black does not violate the restriction for the number of tokens on any row i.

Let White play against this strategy (using the strategy described above).

Since the strategy is computable, the behavior of White is also computable.

One can construct a decompressor V for the strings of length n as follows: each

## COMPLEXITY OF COMPLEXITY AND MAXIMAL C AND K - COMPLEXITY

time White puts a token in a cell (x, i), a program of length i is assigned to x.

By White’s restriction, no more than 2i programs need to be assigned. By universality, a white token on cell (x, i) implies that C (x|n) ≤ i + O(1). If White’s token is alive in (x, i), there is no black token below, so C (x|n) ≥ i, and therefore C (x|n) = i + O(1). Moreover, for a living token, the cell (x, i) is not blackened, so C (i|x) ≥ log n − 1. Therefore, C (C (x|n)|x) ≥ log n − O(1).

Remark: the construction also guarantees that C (x|n) ≥ n/2 − O(1) for that x. (Here the factor 1/2 can be replaced by any α 1 if we change the rules of the game accordingly.) Indeed, according to White’s strategy, he always plays in the highest non-black cell of some column, and at most half of the cells in a column can be blackened, therefore no white tokens appear in the lower half of the board.

1.4. Modiﬁed game and proof of Theorem 1. Now we need to get rid of the condition n and show that for every n there is some x such that C (C (x)|x) ≥ log n − O(1). Imagine that White and Black play simultaneously all the games Gn. Black blackens the cell (x, i) in game G|x| when he discovers that C (i|x) log |x| − 1, as he did before, and puts a black token in a cell (x, i) when he discovers an unconditional program of length i for x. If Black uses this strategy, he satisﬁes the stronger restriction: the total number of tokens in row i on all boards is bounded by 2i.

Assume that White uses the described strategy on each board. What can be said about the total number of white tokens in row i? The dead tokens have black tokens strictly below them and hence the total number of them does not exceed 2i − 1. On the other hand, there is at most one living white token on each board. We know also that in Gn white tokens never appear below row n/2 − 1, so the number of alive white tokens does not exceed 2i + O(1). Therefore we have O(2i ) white tokens on the i-th row in total.

For each n there is a cell (x, i) in Gn where White wins in Gn. Hence, C (x) i+O(1) (because of the property just mentioned and the computability of White’s behavior), C (x) ≥ i and C (i|x) ≥ log n − 1 (by construction of Black’s strategies and the winning condition). Theorem 1 is proven.

1.5. Version for preﬁx complexity.

Theorem 2. There exist some constant c such that for every n there exists a string x of length n such that C (K (x)|x) ≥ log n − c and K (x) ≥ n/2 − c.

This also implies that K (K (x)|x) = log n + O(1).

Pages:   || 2 | 3 |

Similar works:

«Information Operations: What is th.ally support the warfighting CINCs IA-00103 Document created: 2 March 99 Information Assurance the Achilles’ Heel of Joint Vision 2010? CDR Sam Cox, USN MAJ Ron Stimeare, USA MAJ Tim Dean, USA Maj Brad Ashley, USAF Armed Forces Staff College Joint and Combined Staff Officer School Intermediate Course 98-3 Faculty Advisor Jerry Mitchell Seminar 7 Thesis Statement Information Assurance is the Achilles’ Heel of Joint Vision 20 10. Abstract In this paper, we...»

«Archangel Metatron Speaks Channeled by Julie Geigle 12-12-12 Go ahead and rub your hands together if you haven’t already. Place your hands palm up on your lap and feel that energy running through you, from the top of the heavens all the way down to the core, to the center of the Earth. Feel that amazing energy shooting up and down, in and out and all around, weaving a beautiful web connecting each and every one of us across the globe as we come to gather together today for the beautiful...»

«A GAME OF THRONES A Song of Ice and Fire Book I George R.R. Martin CONTENT Map of the NorthMap of the SouthPrologueBranCatelynDaenerysEddardJonCatelynAryaBranTyrionJonDaenerysEddardTyrionCate lynSansaEddardBranCatelynJonEddardTyrionAryaDaenerysBranEddardJonEddardCatelynSansaEddar dTyrionAryaEddardCatelynEddardDaenerysBranTyrionEddardCatelynJonTyrionEddardSansaEddardD aenerysEddardJonEddardAryaSansaJonBranDaenerysCatelynTyrionSansaEddardCatelynJonDaenerys...»

«Bangla We are sorry that you have had a miscarriage A miscarriage can be a distressing experience. You were expecting a baby and you are probably having to cope with all sorts of feelings about this loss. Changes inside your body can also affect the way you are feeling. This leaflet has been written mostly by women who have been through miscarriage themselves. We hope that it will answer some of your questions. Your feelings I feel very upset and depressed. Is this normal? When you started to...»

«Pan-Pacific Association of Applied Linguistics 18(1), 1-17 How Do Learners of English Overcome Non-Understanding?: A Sequential Analysis of ‘English as a Lingua Franca’ Interaction* Hiroki Hanamoto Tokyo Denki University/Graduate School, Kansai University Hanamoto, H. (2014). How do learners of English overcome non-understanding?: A sequential analysis of ‘English as a lingua franca’ interaction. Journal of Pan-Pacific Association of Applied Linguistics, 18(1), 1-17. Although there...»

«S T S M E R K B L AT T HEIMTIERE AGAPORNIDEN Agaporniden Agapornis spp. ISTOCK Allgemeine Informationen Herkunft und Lebensweise: Wilde Agaporniden leben auf dem afrikanischen Festland sowie auf Madagaskar. Die meisten Agapornidenarten kommen mehrheitlich in Steppenund Savannengebieten vor, teilweise sind sie auch im Kulturland anzutreffen. Die beiden Arten Grünköpfchen und Bergpapagei hingegen sind Bewohner von Regenrespektive Bergwäldern. Ausserhalb der Brutzeit sind Agaporniden in...»

«Fundraising Ideas That Work for Grassroots Groups by Ken Wyman, CFRE* Director Ken Wyman and Associates Inc Consultants in Fundraising, Volunteerism, and Communication 64B Shuter Street Toronto, Ontario M5B 1B1 (416) 362-2926 * Certified Fundraising Executive Voluntary Action Program Department of Canadian Heritage Ottawa 1995 Note: This is an updated, expanded and largely revised version of A Guidebook to Fundraising for Disabled Persons' Groups, published in 1988 by the Disabled Persons'...»

«Quaderns. Revista de traducció 7, 2002 121-151 Els Dickens de Josep Carner i els seus crítics1 Marcel Ortín Universitat Pompeu Fabra. Departament de Traducció i Filologia Rambla de Santa Mònica, 30-32. 08002 Barcelona Data de recepció: 5/11/2001 Resum Entre els anys 1928 i 1931, en plena maduresa literària, Josep Carner va ocupar-se en la traducció de tres de les novel·les majors de Dickens: Pickwick Papers, David Copperfield i Great Expectations. Totes tres anaven destinades a la...»

«Notes Eric Blair January 15, 2009 DEAR READER, Many, many people have pointed out that the average person’s attention span has been getting shorter with time. They recommend that you should keep your message short and punchy. Bullet points help; try not to have more than about four bullet points to a slide. To those people, I reply: bite me. You, my intended audience, are educated: you know how to skim for useful information, if a topic interests you then you want it discussed in detail, and...»

«Table of Contents  How Best to Dry Culinary Herbs  Air-Drying Material for Arrangements  Capturing the Elusive Bloom  One Way To Make An Herbal Wreath  Recipe for Potpourri  Basic Dry Potpourri  Bergamot-Rose Potpourri          How Best to Dry Culinary Herbs By Faith Swanson and Lois Ehlenfeldt Can you imagine cutting a handful of rosemary in June and taking it from its storage jar in January nearly as fragrant and savory as the day you cut it? The early method of drying herbs for...»

«Pallid Swift: new to Britain and Ireland W. G. Harvey I n east Kent, 13th May 1978 began cold and damp with a light northwesterly wind and intermittent rain. At dawn, D. Raine and I embarked on a Kent Ornithological Society sponsored bird count through the Stour Valley east of Canterbury. When we reached Stodmarsh at mid morning, there was a perceptible rise in temperature and signs of a break in the clouds which encouraged us to put aside earlier doubts and continue. As we walked along the...»

«Case 12-13262-BLS Doc 1756 Filed 09/19/14 Page 1 of 7 IN THE UNITED STATES BANKRUPTCY COURT FOR THE DISTRICT OF DELAWARE ) In re: ) Chapter 11 ) REVSTONE INDUSTRIES, LLC, et al., ) Case No. 12-13262-BLS ) Debtors. ) (Jointly Administered) ) Hearing Date: 10/1/14 @ 10 a.m. ) Response Deadline: 9/19/14 ) ) Re: Dkt. No. 1670 ) MEDLEY CAPITAL CORPORATION’S RESPONSE TO DEBTORS’ FOURTH OMNIBUS OBJECTION (SUBSTANTIVE) SEEKING TO RECLASSIFY CLAIMS Medley Capital Corporation (“Medley”), by and...»

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