Abstract: Most assertions involving Shannon entropy have their Kolmogorov complexity counterparts. A general theorem of Romashchenko [4] states that every information inequality that is valid in Shannon's theory is also valid in Kolmogorov's theory, and vice verse. In this paper we prove that this is no longer true for ∀ ∃-assertions, exhibiting the first example where the formal analogy between Shannon entropy and Kolmogorov complexity fails.
Publication Year: 2006
Publication Date: 2006-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 11
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot