Семинар лаборатории 1

Доклад посвящён вопросам существования последовательностей, на которые наложены некоторые ограничения: не содержать подслов определённого вида, не содержать данных комбинаций битов в данных позициях и т.п. Достаточно общие утверждения про существование таких последовательностей сводятся, как оказывается, к результатам про колмогоровскую сложность: существованию последовательностей со сложными конечными подпоследовательностями, выбранными определённым образом. Одним из первых результатов такого рода можно считать лемму Левина, которая утверждает, что существует последовательность, все подслова которой имеют большую сложность (не меньшую (1-eps)n-O(1), где eps - фиксированная маленькая константа, а n - длина подслова). В докладе будут приведены различные обобщения этой леммы, а также их применения: существование последовательностей с заданной критической экспонентой, существование почти периодических последовательностей со сложными подсловами и другие.