Существуют ли теоретические формулировки узлов полных задач NP?

Существуют ли NP-полные (или даже NP-сложные, или NP) задачи, которые имеют хорошие топологические свойства для изучения. Есть ли у задач NP теоретические формулировки узлов? Мы знаем о результатах # о полиноме Джонса. Графические задачи (вложения?), В частности раскраски графов, могут иметь хорошие теоретические свойства узлов. Это открытый вопрос, и любые ссылки на эту тему приветствуются. $P$

ct.category-theory np user3483902
источник

Ответы:

Вы можете взглянуть на:

Питер Голбус, Роберт В. Макгрейл, Томаш Пшицкий, Мэри Шарак и Александр Чакаров. 2009. Трехцветные торические узлы NP-полны . В материалах 47-й ежегодной юго-восточной региональной конференции (ACM-SE 47). ACM, Нью-Йорк, Нью-Йорк, США, статья 42, 6 стр.

Аннотация: В данной работе представлен метод связывания класса задач удовлетворения ограничений с трехмерным узлом. Учитывая узел, можно построить узел узлов, который обычно является бесконечной свободной алгеброй. Желаемый набор задач выводится из набора инвариантных отношений над квандлом узла, применяя теорию, которая связывает конечные алгебры с проблемами удовлетворения ограничений. Это позволяет нам развивать представления о податливых и NP-полных квандлах и узлах. В частности, мы показываем, что все трехцветные торические узлы и все, кроме не более 2 нетривиальных узлов с 10 или менее пересечениями, являются NP-полными.

а также к своему основному докладу:

P. Golbus, RW McGrail, M. Merling, K. Ober, M. Sharac и J. Wood. Класс проблем удовлетворения ограничений над узлом . Технический отчет № BARD-CMSC-2008-01, Bard College, 2008.

Марцио де Биаси
источник

В первом абзаце есть несколько ссылок

Марк Лакенби. Верхняя граница полинома для Рейдемейстера движется. Arxiv: 1302.0180

$\mathbf{NP} \cap \mathbf{coNP}$

Джоэл Хасс, Джеффри С. Лагариас, Николас Пиппенгер. Вычислительная сложность проблем узлов и связей. J. ACM 46 (1999) 185-211. Arxiv: математика / 9807016
Грег Куперберг. Узловатость есть в NP, по модулю GRH. Декабрь 2011 г., пересмотрено в январе 2014 г. arXiv: 1112.0845

$g$

Ян Агол, Джоэл Хасс, Уильям Терстон. 3-КОЛЛЕКЦИОННЫЙ УЗЕЛ GENUS является NP-полным. STOC 2002. ACM ссылка

Меня интересуют и другие примеры.

Ноам Цайлбергер
источник

Никогда не публиковавшиеся доказательства NP-Агола с использованием зашитых иерархий кратко резюмируются в недавнем опросе Лакенби

Арно,

R^{3}

$\mathbb{R}^3$

R^{3}

$\mathbb{R}^3$

S^{3}

$\mathbb{S}^3$

спасибо за вашу точность: я включил его в текст.

Ноам Цайлбергер,

Может быть, здесь плотность, но не ясно, почему результаты характеризуются в ответе тем, что говорят о сучковатости / незаузленности «быть NP-твердым», а не «быть в NP», поскольку, насколько я могу видеть в резюме, они утверждают что проблемы в NP, но не в том, что они также NP-Complete.

Абель Молина

нет, ты прав, я просто был дремучим. Исправлено сейчас.

Ноам Цайлбергер