✦ LIBER ✦

Kolmogorov complexity and random graphs

✍ Scribed by W.W. Kirchherr

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 445 KB
Volume: 41
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(92)90040-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Kolmogorov complexity of random real

The Kolmogorov complexity of random reals

✍ Liang Yu; Decheng Ding; Rodney Downey 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 296 KB

Kolmogorov random graphs only have trivi

Kolmogorov random graphs only have trivial stable colorings

✍ Qi Cheng; Fang Fang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 52 KB

In this paper, we prove that random graphs only have trivial stable colorings. Our result improves Theorem 4.1 in [Proc.

Kolmogorov Complexity and Noncomputabili

Kolmogorov Complexity and Noncomputability

✍ George Davie 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB

Kolmogorov–Loveland randomness and stoch

Kolmogorov–Loveland randomness and stochasticity

✍ Wolfgang Merkle; Joseph S. Miller; André Nies; Jan Reimann; Frank Stephan 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 381 KB

Inequalities for Shannon Entropy and Kol

Inequalities for Shannon Entropy and Kolmogorov Complexity

✍ Daniel Hammer; Andrei Romashchenko; Alexander Shen; Nikolai Vereshchagin 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 272 KB

It was mentioned by Kolmogorov (1968, IEEE Trans. Inform. Theory 14, 662 664) that the properties of algorithmic complexity and Shannon entropy are similar. We investigate one aspect of this similarity. Namely, we are interested in linear inequalities that are valid for Shannon entropy and for Kolmo

A note on Kolmogorov complexity and entr

A note on Kolmogorov complexity and entropy

✍ Yasuichi Horibe 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 105 KB