Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T05:37:01.116Z Has data issue: false hasContentIssue false

COMPLEXITY OF COMPLEXITY AND STRINGS WITH MAXIMAL PLAIN AND PREFIXKOLMOGOROV COMPLEXITY

Published online by Cambridge University Press:  25 June 2014

B. BAUWENS
Affiliation:
LORIA, UNIVERSITÉ DE LORRAINE 615-B248 RUE DU JARDIN BOTANIQUE 54506 VANDŒVRE-LÈS-NANCY, FRANCEURL: www.bcomp.be. E-mail:brbauwens@gmail.com
A. SHEN
Affiliation:
LIRMM CNRS & UNIVERSITY OF MONTPELLIER 2. UMR 5506 - CC477, 161 RUE ADA 34095 MONTPELLIER CEDEX 5 FRANCE, ON LEAVE FROM IITP RAS MOSCOWE-mail:alexander.shen@lirmm.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Péter Gács showed (Gács 1974) that for everyn there exists a bit string x of lengthn whose plain complexityC(x) has almost maximal conditional complexityrelative to x, i.e., $C\left( {C\left( x \right)|x} \right) \ge {\rm{log}}n - {\rm{log}}^{\left( 2 \right)} n - O\left( 1 \right)$ (Here ${\rm{log}}^{\left( 2 \right)} i = {\rm{loglog}}i$.) Following Elena Kalinina (Kalinina 2011), we provide a simplegame-based proof of this result; modifying her argument, we get a better (andtight) bound ${\rm{log}}n - O\left( 1 \right)$ We also show the same bound for prefix-free complexity.

Robert Solovay showed (Solovay 1975) that infinitely many stringsx have maximal plain complexity but not maximal prefixcomplexity (among the strings of the same length): for some cthere exist infinitely many x such that $|x| - C\left( x \right) \le c$ and $|x| + K\left( {|x|} \right) - K\left( x \right) \ge {\rm{log}}^{\left( 2 \right)} |x| - c{\rm{log}}^{\left( 3 \right)} |x|$ In fact, the results of Solovay and Gács are closelyrelated. Using the result above, we provide a short proof forSolovay’s result. We also generalize it by showing that for somec and for all n there are stringsx of length n with $n - C\left( x \right) \le c$ and $n + K\left( n \right) - K\left( x \right) \ge K\left( {K\left( n \right)|n} \right) - 3K\left( {K\left( {K\left( n \right)|n} \right)|n} \right) - c.$ We also prove a close upper bound $K\left( {K\left( n \right)|n} \right) + O\left( 1 \right)$

Finally, we provide a direct game proof for Joseph Miller’sgeneralization (Miller 2006) of the same Solovay’s theorem: if aco-enumerable set (a set with c.e. complement) contains for every length astring of this length, then it contains infinitely many stringsx such that$|x| + K\left( {|x|} \right) - K\left( x \right) \ge {\rm{log}}^{\left( 2 \right)} |x| - O\left( {{\rm{log}}^{\left( 3 \right)} |x|} \right).$

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2014