А.Е.Ромащенко

Сложностная интерпретация задачи о вилочной сети

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