|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Non-reducible descriptions for conditional Kolmogorov complexityстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Дата последнего поиска статьи во внешних источниках: 27 мая 2015 г.
- Авторы: Muchnik Andrej, Shen Alexander, Ustinov Mikhail, Vereshchagin Nikolai, Vyugin Michael
- Сборник: Theory and Applications of Models of Computation, Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006,
- Серия: Lecture Notes in Computer Science
- Том: 3959
- Год издания: 2006
- Издательство: SPRINGER-VERLAG BERLIN
- Местоположение издательства: HEIDELBERGER PLATZ 3, BERLIN, GERMANY,D-14197
- Первая страница: 15
- Последняя страница: 20
- DOI: 10.1007/11750321_29
- Аннотация: Let a program p on input a outputs b. We are looking for a shorter program p′ having the same property (p′(a)=b). In addition, we want p′ to be simple conditional to p (this means that the conditional Kolmogorov complexity K (p ′|p) is negligible). In the present paper, we prove that sometimes there is no such program p′, even in the case when the complexity of p is much bigger than K (b|a). We give three different constructions that use the game approach, probabilistic arguments and algebraic (combinatorial) arguments, respectively.
- Добавил в систему: Верещагин Николай Константинович