Laboratory of Mathematical Logic at PDMI

Пятница, 23 апреля, ауд. 106. Начало в 18:00.

Докладчик: А. Бешенов (Липецк).

Тема: Вычислительная сложность задач об узлах и зацеплениях.

Abstract

Зацепления--- это вложения суммы окружностей $S^1$ в
$\mathbb{R}^3$ (или в другое трехмерное
многообразие). Зацепление, включающее одну компоненту,
называется узлом.

Для узла естественно возникает задача распознавания
тривиальности (можно ли его развязать), а для
зацепления--- задача разводимости (можно ли
разделить компоненты).

Разрешимость основных задач была установлена благодаря
теории нормальных поверхностей, развитой Хакеном в
50--60-е годы, однако долгое время не имелось никаких оценок
сложности.

При помощи хакеновских алгоритмов в статье
[Hass--Lagarias--Pippenger] было доказано, что распознавание
тривиального узла и распознавание разводимости зацепления
лежат в классе $\mathbf{NP}$. В [Agol--Hass--Thurston] среди
более общих задач была даже найдена $\mathbf{NP}$-полная~---
оценка рода узла на произвольном трехмерном многообразии.

Сложность задач об узлах и зацеплениях~---
это область активных исследований, в докладе будет рассказано об истории,
известных результатах и гипотезах.

Доклад будет сконцентрирован на сложностных и
алгоритмических аспектах.

Основные источники:

Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger.
The computational complexity of knot and link problems.
http://arxiv.org/abs/math/9807016

Ian Agol, Joel Hass, William Thurston.
The computational complexity of knot genus and spanning area.
http://arxiv.org/abs/math/0205057