Upper semi-lattice of binary strings with the relation "x is simple conditional to y"

Alexey Chernov, Andrej Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai Vereshchagin

Research output: Contribution to journalArticle

Abstract

In this paper we construct a structure R that is a “finite version” of the semi-lattice of Turing degrees. Its elements are strings (technically, sequences of strings) and x `<=` y means that K(x|y)=(conditional Kolmogorov complexity of x relative to y) is small. We construct two elements in R that do not have greatest lower bound. We give a series of examples that show how natural algebraic constructions give two elements that have lower bound 0 (minimal element) but significant mutual information. (A first example of that kind was constructed by Gács–Körner(Problems Control Inform. Theory 2 (1973) 149) using a completely different technique.) Wede4ne a notion of “complexity profile” of the pair of elements of R and give (exact) upper andlower bounds for it in a particular case.
Original languageEnglish
Pages (from-to)69-95
Number of pages27
JournalTheoretical Computer Science
Volume271
Issue number1-2
DOIs
Publication statusPublished - 28 Jan 2002

Keywords

  • Kolmogorov complexity
  • common information
  • conditional complexity

Fingerprint Dive into the research topics of 'Upper semi-lattice of binary strings with the relation "x is simple conditional to y"'. Together they form a unique fingerprint.

  • Cite this