Монотонное упрощение зацеплений и лежандровы графы

Аннотация

Актуальность темы. Теория узлов — классический раздел топологии, который развивается с конца XIX века. Фундаментальный вопрос этой теории — это классификация узлов и зацеплений в трёхмерном пространстве. Задача распознавания узла и, в частности, тривиального узла алгоритмически решена. Решение предложил Вольфганг Хакен 1 2 в 1961 году. Его идею довели до строгого доказательства усилия многих математиков. Однако этот алгоритм очень медленный. Теоретическая оценка на время его работы — двойная экспонента от сложности узла. Хотелось бы найти полиномиальный алгоритм или доказать, что его нет. В связи с этим опишем предпочтительную классификацию узлов и зацеплений: функция сложности на множестве представителей, конечный набор канонических представителей и преобразование любого представителя к каноническому, не увеличивающее сложность. Такие преобразования мы будем называть монотонными упрощениями или просто упрощениями. Рассмотрим пример представления узлов плоскими диаграммами. Сложность плоской диаграммы — количество перекрёстков. Теорема Райдемайстера описывает три простых движения, которые переводят плоскую диаграмму узла в любую другую. Однако тривиальный узел обладает бесконечным числом монотонно неупрощаемых плоских диаграмм: например, диаграмма на рисунке 1 и любая её кратная сумма с собой. Это говорит о том, что подход плоских диаграмм не вписывается в предпочтительную классификацию.