Можно ли распознать неузлы за полиномиальное время?
В математике , то незаузленность проблема проблема алгоритмического распознавания тривиального , учитывая некоторое представление узла, например, диаграммы узла . Есть несколько типов алгоритмов развязывания узлов. Основная нерешенная проблема состоит в том, чтобы определить, допускает ли проблема алгоритм полиномиального времени ; то есть ли проблема заключается в классовой сложности P .
Вычислительная сложность
Первые шаги к определению вычислительной сложности были предприняты для доказательства того, что проблема относится к классам большей сложности, которые содержат класс P. Используя нормальные поверхности для описания поверхностей Зейферта данного узла, Хасс, Лагариас и Пиппенгер (1999) показали, что проблема развязывания находится в классе сложности NP . Хара, Тани и Ямамото (2005) заявили, что более слабый результат заключается в том, что развязывание узлов происходит в AM ∩ co-AM ; Однако позже они отказались от этого иска. [1] В 2011 году Грег Куперберг доказал, что (в предположении обобщенной гипотезы Римана ) проблема несвязанности находится в совместной NP , [2] а в 2016 году Марк Лакенби предоставил безусловное доказательство членства в совместной NP. [3]
Проблема незаузленности имеет ту же вычислительную сложность , как тестирование вложение в том неориентированного графа в евклидовом пространстве является linkless . [4]
Например, один из узлов Очиай с 139 вершинами [5] был первоначально распущен компьютером за 108 часов [6], но в более поздних исследованиях это время было сокращено до 10 минут. [7]
Алгоритмы развязывания
Несколько алгоритмов, решающих проблему развязывания узлов, основаны на теории нормальных поверхностей Хакена :
- Алгоритм Хакена использует теорию нормальных поверхностей, чтобы найти диск, граница которого является узлом. Изначально Хакен использовал этот алгоритм, чтобы показать, что распутывание узлов разрешимо, но не анализировал его сложность более подробно.
- Хасс, Лагариас и Пиппенгер показали, что множество всех нормальных поверхностей может быть представлено целыми точками в многогранном конусе и что поверхность, свидетельствующая о незаузленности кривой (если она существует), всегда может быть найдена на одном из крайних лучей. этого конуса. Следовательно, можно использовать методы перечисления вершин, чтобы перечислить все крайние лучи и проверить, соответствует ли какой-либо из них ограничивающему кругу узла. Хасс, Лагариас и Пиппенгер использовали этот метод, чтобы показать, что незаузлованность заключается в NP; более поздние исследователи, такие как Burton (2011a), уточнили свой анализ, показав, что этот алгоритм может быть полезным (хотя и не с полиномиальным временем), поскольку его сложность является одноэкспоненциальной функцией низкого порядка от числа пересечений.
- Алгоритм Бирмана и Хирша (1998) использует слоения кос , несколько иной тип структуры, чем нормальная поверхность. Однако для анализа его поведения они возвращаются к теории нормальной поверхности.
Другие подходы включают:
- Количество ходов Райдемейстера, необходимых для преобразования диаграммы без узлов в стандартную диаграмму с узлами, не превышает полиномиального числа пересечений. [8] Следовательно, перебор всех последовательностей движений Рейдемейстера может обнаружить незаузлованность в экспоненциальном времени.
- Точно так же любые две триангуляции одного и того же узлового дополнения могут быть соединены последовательностью ходов Пахнера, длина которых не более чем в два раза превышает экспоненциальную по количеству пересечений. [9] Таким образом, можно определить, является ли узел неузлом, проверяя все последовательности ходов Пахнера этой длины, начиная с дополнения данного узла, и определяя, преобразует ли какое-либо из них дополнение в стандартную триангуляцию полноторий . Время для этого метода будет трехкратно экспоненциальным; однако экспериментальные данные показывают, что эта граница очень пессимистична и что требуется гораздо меньше ходов Пахнера. [10]
- Любое дуговое представление узла можно монотонно упростить до минимального с помощью элементарных ходов. [11] Таким образом, перебор методом перебора среди всех представлений дуги не большей сложности дает одноэкспоненциальный алгоритм для задачи развязывания узлов.
- Финитный из группы узла (что следует из геометризации из Хакен многообразий ) дает алгоритм: чек , если группа имеет нециклический конечную группу фактор. Эта идея используется в результате Куперберга о том, что проблема развязывания узлов находится в совместной NP.
- Узел Гомология Floer узла определяет род узла, который равен 0 тогда и только тогда, когда узел является безузлом. Комбинаторная версия гомологии узла Флоера позволяет ее вычислить ( Manolescu, Ozsváth & Sarkar 2009 ).
- Хованы гомология определяет тривиальную согласно результату Kronheimer и Mrówka . [12] Сложность гомологии Хованова по крайней мере так же высока, как # P-сложная задача вычисления многочлена Джонса , но она может быть вычислена на практике с использованием алгоритма и программы Бар-Натана (2007) . Бар-Натан не дает строгого анализа своего алгоритма, но эвристически оценивает его как экспоненциальную зависимость от ширины пути диаграммы пересечений, которая, в свою очередь, не более чем пропорциональна квадратному корню из числа пересечений.
Понимание сложности этих алгоритмов - активная область исследований.
Смотрите также
- Алгоритмическая топология
- Несвязанный номер
Заметки
- ↑ Упоминается как «личное общение» в [15] Куперберга (2014) .
- ^ Куперберг (2014)
- ^ Лакенби (2016)
- ^ Kawarabayashi, Крейцер и Mohar (2010) .
- ^ Очиаи, М. (1990). «Нетривиальные проекции тривиального узла» (PDF) . SMF Asterisque . 192 : 7–9.
- ^ Grzeszczuk, R .; Хуанг, М .; Кауфман, Л. (1997). «Физически обоснованное стохастическое упрощение математических узлов». IEEE Transactions по визуализации и компьютерной графике . 3 (3): 262–278. DOI : 10.1109 / 2945.620492 .
- ^ Лэдд & Kavraki (2004) .
- ^ Lackenby (2015) .
- ^ Миятович (2005) .
- ^ Бертон (2011b) .
- ^ Дынников (2006) .
- ^ Kronheimer & Мровка (2011)
Рекомендации
- Бар-Натан, Дрор (2007), "Быстрый Хованов гомология вычисление", Журнал теории узлов и ее ответвлений , 16 (3): 243-255, Arxiv : math.GT/0606318 , DOI : 10,1142 / S0218216507005294 , MR 2320156 , S2CID 17036344.
- Бирман, Джоан С .; Хирш, Майкл (1998), «Новый алгоритм распознавания узлов», Геометрия и топология , 2 : 178–220, arXiv : math / 9801126 , doi : 10.2140 / gt.1998.2.175 , S2CID 17776505.
- Бертон, Бенджамин А. (2011a), «Максимальные допустимые грани и асимптотические границы для пространства решений нормальной поверхности» (PDF) , Журнал комбинаторной теории , серия A, 118 (4): 1410–1435, arXiv : 1004.2605 , doi : 10.1016 / j.jcta.2010.12.011 , Руководство по эксплуатации 2763065 , S2CID 11461722.
- Бертон, Бенджамин (2011b), "Граф Пахнера и упрощение трехсферных триангуляций", Proc. 27-й симпозиум ACM по вычислительной геометрии , стр. 153–162, arXiv : 1011.4169 , doi : 10.1145 / 1998196.1998220 , S2CID 382685.
- Дынников, Иван (2006), "Arc-презентации ссылок: монотонное упрощение", Fundamenta Mathematicae , 190 : 29–76, arXiv : math / 0208153 , doi : 10.4064 / fm190-0-3 , S2CID 14137437.
- Хакен, Вольфганг (1961), "Теорье дер Normalflächen", Acta Mathematica , 105 : 245-375, DOI : 10.1007 / BF02559591.
- Хара, Масао; Тани, Сейичи; Ямамото, Макото (2005), «Распутывание узлов в AM ∩ co-AM», Proc. 16-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '05) , стр. 359–364.
- Хасс, Джоэл ; Лагариас, Джеффри К .; Пиппенгер, Николас (1999), "Вычислительная сложность проблем узлов и ссылок", Журнал ACM , 46 (2): 185–211, arXiv : math / 9807016 , doi : 10.1145 / 301970.301971 , MR 1693203 , S2CID 125854.
- Хасс, Джоэл ; Лагариас, Джеффри К. (2001), «Число ходов Рейдемейстера, необходимых для развязывания узлов», Журнал Американского математического общества , 14 (2): 399–428, arXiv : math / 9807012 , doi : 10.1090 / S0894-0347- 01-00358-7 , Руководство по ремонту 1815217 , S2CID 15654705.
- Каварабаяси, Кен-ичи ; Крейцер, Стефан; Мохар, Боян (2010), «Беззвучные и плоские вложения в 3-мерное пространство и проблема без узлов» (PDF) , Proc. ACM симпозиум по вычислительной геометрии (SoCG '10) . С. 97-106, DOI : 10,1145 / 1810959,1810975 , S2CID 12290801.
- Кронхеймер, Питер; Mrowka, Tomasz (2011), «Гомология Хованова - это детектор узлов», Publications Mathématiques de l'IHÉS , 113 (1): 97–208, arXiv : 1005.4346 , doi : 10.1007 / s10240-010-0030-y , S2CID 119586228
- Kuperberg, Грег (2014), "Knottedness в НП, по модулю GRH", Прогресс в области математики , 256 : 493-506, Arxiv : 1112.0845 , DOI : 10.1016 / j.aim.2014.01.007 , МР 3177300 , S2CID 12634367.
- Lackenby, Марк (2015), "Полином верхней границы Радемайстер двигается", Анналы математики , вторая серия, 182 (2): 491-564, Arxiv : 1302.0180 , DOI : 10.4007 / annals.2015.182.2.3 , MR 3418524 , S2CID 119662237.
- Lackenby, Marc (2016), Эффективная сертификация узловатости и нормы Терстона , arXiv : 1604.00290 , Bibcode : 2016arXiv160400290L.
- Лэдд, Эндрю М .; Кавраки, Лидия Э. (2004), «Планирование движения для распутывания узлов» (PDF) , в Буассонна, Жан-Даниэль; Бердик, Джоэл; Гольдберг, Кен; Хатчинсон, Сет (ред.), Алгоритмические основы робототехники V , Springer Tracts in Advanced Robotics, 7 , Springer, стр. 7–23, DOI : 10.1007 / 978-3-540-45058-0_2.
- Манолеску, Чиприан ; Озсват, Питер С .; Саркар, Сухарит (2009), «Комбинаторное описание узловых гомологий Флора», Annals of Mathematics , Second Series, 169 (2): 633–660, arXiv : math / 0607691 , Bibcode : 2006math ...... 7691M , DOI : 10.4007 / annals.2009.169.633 , MR 2480614 , S2CID 15427272.
- Миятович, Александар (2005), "Простые структуры узловых дополнений", Mathematical Research Letters , 12 (6): 843–856, arXiv : math / 0306117 , doi : 10.4310 / mrl.2005.v12.n6.a6 , MR 2189244 , S2CID 7726354
Внешние ссылки
- Complexity Zoo предоставляет информацию о классах сложности и их отношениях включения.