Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y"

Авторы: Muchnik Andrei A., Romashchenko Andrei E., Shen Alexander, Vereshchagin Nikolai K.
Сборник: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999
Год издания: 1999
Место издания: IEEE Computer Society
Первая страница: 114
Последняя страница: 123
DOI: 10.1109/CCC.1999.766270
Аннотация: In this paper we construct a structure R that is a “finite version” of the semilattice of Turing degrees. Its elements are strings (technically, sequences of strings) and x⩽y means that K(x|)=(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 O (minimal element) but significant mutual information. (A first example of that kind was constructed by Gacs-Korner (1973) using completely different technique.) We define a notion of “complexity profile” of the pair of elements of R and give (exact) upper and lower bounds for it in a particular case.
Добавил в систему: Верещагин Николай Константинович

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

ИСТИНА