Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Theory of Computing Systems
Published in: Theory of Computing Systems 2/2017

19-03-2016

Sophistication vs Logical Depth

Authors: Luís Antunes, Bruno Bauwens, André Souto, Andreia Teixeira

Published in: Theory of Computing Systems | Issue 2/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program that is shortest within some precision. We show that the Busy Beaver function of the sophistication of a string exceeds its logical depth with logarithmically bigger precision, and that logical depth exceeds the Busy Beaver function of sophistication with logarithmically bigger precision. We also show that sophistication is unstable in its precision: constant variations can change its value by a linear term in the length of the string.
previous article The Complexity of Finding Effectors
next article A Difference in Complexity Between Recursion and Tail Recursion

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
In fact the proof only requires that U and V are optimal, i.e. for all machines W there exist c W such that C U (x) ≤ C W (x)+c W and similarly for V.
 
2
For any ε> 0, we can replace the term \(\tfrac {3}{4}|x|\) by (1−ε)|x| if the significance of the second sophistication term is replaced by \(c + O(\log (c/\varepsilon ))\).
 
3
On the other hand, any set must have non-typical elements unless the set contains a lot of mutual information with the Halting problem [17].
 
4
The Kolmogorov complexity of a set is the length of a shortest program that prints all its elements and halts.
 
5
Partition the set in subsets of size at most 2 j−k , this increases the complexity of the x-containing set by at most k.
 
6
Theorem IV.4 in [14] states that every decreasing function f is \((C(f)+O(\log |x|))\)-close to the function
$$\lambda_{x}(k) = \min \left\{ C(S) + \log |S|: S \ni x \wedge C(x) \le k \right\} $$
of some string of length f(0). (We use plain complexity in the definition of λ x , because all results hold up to \(O(\log |x|)\) terms). For fixed x, the function λ x is the inverse of \(\text {soph}_{x}^{\text {Set}}\).
 
7
This probabilistic sufficiency criterion was defined in [20] in terms of prefix-free complexity, because 2−K(x|P) defines a probability distribution and hence, it is natural to compare it with P(x). Prefix complexity and plain complexity differ by at most \(O(\log |x|)\) [12], and this precision is sufficient for our discussion.
 
8
It is unclear whether H(x) = K m(x) + O(1).
 
9
The definition of total entropy used in [27,28] is K(P) + H(P). Notice that plain and prefix complexity are close (\(|K(P) - C(P)| \le O(\log C(P)\)). See also footnote 7.
 
10
In fact, in [27] the precision for which these inequalities should hold is not discussed. Also, the authors suggest that the computation time of a program for P is bounded by some computable function. In [29] the first requirement c = δ|x| is chosen for some δ > 0 and in the second requirement a different parameter is chosen. Furthermore, P should be computable as a real function and no restrictions on the computation time are considered. Also, K(P) was replaced by K(P, H(P)).
 
11
Indeed, if P is c-good then it is (2c)-sufficient. For the other direction, note that at most 2 H(P) + c+1 elements satisfy \(\log (1/P(x)) \le \lceil H(P) \rceil + c\), and these elements can be computed given P and ⌈H(x)⌉≤C(x) + c ≤ |x| + c + O(1). Hence a c-good model defines a \((c+O(\log |x|))\)-sufficient set.
 
12
The formulation of Theorem 3.2.2 in [30] uses I(x;H) = K(x)−K H (x) with K H (x) the Kolmogorov complexity on a machine that has an oracle for the Halting problem. To obtain Theorem 7 from this, use the folklore result: \(\text {depth}_{0}(x) \ge I(x;H) + O(\log I(x;H))\).
 
Literature
1.
2.
Kolmogorov, A.: Three approaches to the quantitative definition of information. Problemy Peredachi Informatsii 1(1), 3–11 (1965)MathSciNetMATH
3.
4.
Bennett, C.: Logical Depth and Physical Complexity, pp 227–257. Oxford University Press, Inc., New York (1988)MATH
5.
Antunes, L., Fortnow, L., van Melkebeek, D., Vinodchandran, N.V.: Computational depth: concept and applications. Theor. Comput. Sci. 354(3), 391–404 (2006)MathSciNetCrossRefMATH
6.
7.
8.
Kolmogorov, A.N.: Talk in Information Theory Symposium. In: Tallinn, Estonia (1973)
9.
Kolmogorov, A.N.: Complexity of algorithms and objective definition of randomness. Uspekhi Mat. Nauk 29(4), 155 (1974)
10.
Koppel, M.: Structure. In: Herken, R. (ed.) The Universal Turing Machine: a Half-Century Survey, 2nd edition, pp 403–419. Springer (1995)
11.
Koppel, M., Atlan, H.: An almost machine-independent theory of program-length complexity, sophistication, and induction. Inf. Sci. 56(1-3), 23–33 (1991). Elsevier Science Publishers Ltd.MathSciNetCrossRefMATH
12.
Li, Ming, Vitányi, P.: An Introduction to Kolmogorov Complexity and its Applications. Springer (2008)
13.
14.
Vereshchagin, N., Vitanyi, P.: Kolmogorov’s structure functions and model selection. IEEE Trans. Inf. Theory 50, 3265–3290 (2004). Computer SocietyMathSciNetCrossRefMATH
15.
Li, Ming, Vitányi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer (1997)
16.
Cover, T., Gacs, P., Gray, R.M.: Kolmogorov’s contributions to information theory and algorithmic complexity. Ann. Probab. 17(3), 840–865 (1989)MathSciNetCrossRefMATH
17.
18.
Shen, A.: The concept of (alpha, beta)-stochasticity in the kolmogorov sense and its properties. Soviet Mathematics Doklady 28(1), 295–299 (1983)MATH
19.
Vyugin, V.: On the defect of randomness of a finite object with respect to measures with given complexity bounds. Theory Prob. Appl. 32(3), 508–512 (1987)CrossRef
20.
21.
Cover, T.: The Impact of Processing Techniques on Communications. chapter Kolmogorov Complexity, Data Compression and Inference., pages 23–33. J. Skwyrzynski. Martinus Nijhoff Publishers (1985)
22.
Cover, T., Joy, T.: Elements of Information Theory. Wiley (1991)
23.
24.
Shen, A.: Algorithmic statistics: main results. In preparation (2013)
25.
Vereshchagin, N.: Algorithmic minimal sufficient statistic revisited. Mathematical Theory and Computational Practice, 478–487 (2009)
26.
Verschagin, N.: On Algorithmic Strong Sufficient Statistics. In: Proceedings of Computability in Europe (2013)
27.
28.
Gell-Mann, M., Lloyd, S.: Effective complexity. Nonextensive entropy, 387–398 (2004)
29.
Nihat, A., Muller, M., Szkola, A.: Effective complexity and its relation to logical depth. IEEE Trans. Inf. Theory 56(9), 4593–4607 (2010)MathSciNetCrossRef
30.
Bauwens, B.: Computability in statistical hypotheses testing, and characterizations of independence and directed influences in time series using Kolmogorov complexity. PhD thesis, Ugent (2010)
31.
Vereshchagin, N., Shen, A.: Algorithmic statistics revisited (2015). arXiv preprint arXiv:1504.​04950
Metadata
Title
Sophistication vs Logical Depth
Authors
Luís Antunes
Bruno Bauwens
André Souto
Andreia Teixeira
Publication date
19-03-2016
Publisher
Springer US
Published in
Theory of Computing Systems / Issue 2/2017
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-016-9672-6

Other articles of this Issue 2/2017

Theory of Computing Systems 2/2017 Go to the issue

OriginalPaper

Composition Closure of Linear Extended Top-down Tree Transducers

OriginalPaper

Fixed Points, Nash Equilibria, and the Existential Theory of the Reals

OriginalPaper

Path-Disruption Games: Bribery and a Probabilistic Model

OriginalPaper

The Behavior of Clique-Width under Graph Operations and Graph Transformations

OriginalPaper

Distance Vector-based Advance Reservation with Delay Performance Guarantees

OriginalPaper

The Complexity of Finding Effectors

Premium Partner

    Image Credits