Independent Minimum Length Programs to Translate between Given Strings

Авторы: Vereshchagin Nikolai K., Vyugin Michael V.
Сборник: Proceedings 15th Annual IEEE Conference on Computational Complexity
Год издания: 2000
Первая страница: 138
Последняя страница: 145
DOI: 10.1109/CCC.2000.856744
Аннотация: A string p is called a program to compute y given x if U(p; x) =y, where U denotes universal programming language. Kolmogorov complexity K(y\x) of y relative to x is defined as minimum length of a program to compute y given x. Let K(x) denote K(x\empty string) (Kolmogorov complexity of x) and let I(x : y) = K(x) +K(y) - K({x; y}) (the amount of mutual information in x; y). In the present paper we answer in negative the following question posed in [1]: Is it true that for any strings x; y there are independent minimum length programs p; q to translate between x; y, that is, is it true that for any x; y there are p; q such that U(p; x) =y, U(q; y) =x, the length of p is K(y\x), the length of q is K(x\y), and I(p : q) = 0(where the last three equalities hold up to an additive O(log(K(x\y)+K(y\x))) term)?
Добавил в систему: Верещагин Николай Константинович

	ИСТИНА	Войти в систему Регистрация
	ИПМех РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА