Вычислительная топология

Алгоритмическая топология , или вычислительная топология , — это подраздел топологии , пересекающийся с областями информатики , в частности, с вычислительной геометрией и теорией сложности вычислений .

Основной задачей алгоритмической топологии, как следует из ее названия, является разработка эффективных алгоритмов для решения проблем, которые естественным образом возникают в таких областях, как вычислительная геометрия , графика , робототехника , социальные науки , структурная биология и химия , используя методы вычислимой топологии . ^[1]^[2]^[3]

Основные алгоритмы по предметным областям [ править ]

Алгоритмическая теория трёх многообразий [ править ]

Большое семейство алгоритмов, касающихся 3-многообразий , вращается вокруг теории нормальных поверхностей , которая включает в себя несколько методов превращения проблем теории 3-многообразий в задачи целочисленного линейного программирования.

Алгоритм трехсферного распознавания Рубинштейна и Томпсона . Это алгоритм, который принимает в качестве входных данных триангулированное 3-многообразие ли это многообразие и определяет, гомеоморфно 3 -сфере . Он имеет экспоненциальное время выполнения по числу тетраэдрических симплексов в исходном 3-многообразии, а также экспоненциальный профиль памяти. Более того, это реализовано в программном комплексе Regin . ^[4] Саул Шлеймер далее показал, что проблема заключается в классе сложности NP . ^[5] Более того, Рафаэль Центнер показал, что проблема заключается в классе сложности coNP, ^[6] при условии, что справедлива обобщенная гипотеза Римана. Он использует инстантонную калибровочную теорию, теорему геометризации трехмерных многообразий и последующие работы Грега Куперберга. ^[7] по сложности обнаружения заученности.
Разложение по соединительной сумме трехмерных многообразий также реализовано в Regina , имеет экспоненциальное время выполнения и основано на алгоритме, аналогичном алгоритму распознавания трехсфер.
Определение того, что 3-многообразие Зейферта-Вебера не содержит несжимаемой поверхности, было алгоритмически реализовано Бертоном, Рубинштейном и Тиллманном. ^[8] и основан на теории нормальной поверхности.
Алгоритм Мэннинга — это алгоритм поиска гиперболических структур на трехмерных многообразиях, фундаментальная группа которых имеет решение проблемы слов . ^[9]

В настоящее время разложение JSJ не реализовано алгоритмически в компьютерном программном обеспечении. Не имеет значения и разложение тела сжатия. Существуют некоторые очень популярные и успешные эвристики, такие как SnapPea , которая с большим успехом вычисляет приближенные гиперболические структуры на триангулированных трехмерных многообразиях. Известно, что полную классификацию 3-многообразий можно выполнить алгоритмически: ^[10] на самом деле известно, что решение о том, являются ли два замкнутых ориентированных 3-многообразия, заданных триангуляциями (симплициальными комплексами), эквивалентными (гомеоморфными), является элементарно-рекурсивным . ^[11] Это обобщает результат о 3-сферном распознавании.

Алгоритмы преобразования [ править ]

SnapPea реализует алгоритм преобразования плоского узла или диаграммы связей в триангуляцию с точками возврата. Этот алгоритм имеет примерно линейное время выполнения по количеству пересечений на диаграмме и небольшой профиль памяти. Алгоритм аналогичен алгоритму Виртингера для построения представлений фундаментальной группы дополнений ссылок, заданных плоскими диаграммами. Аналогично, SnapPea может преобразовывать хирургические представления 3-многообразий в триангуляции представленного 3-многообразия.
Д. Терстон и Ф. Костантино разработали процедуру построения триангулированного 4-многообразия из триангулированного 3-многообразия. Точно так же его можно использовать для построения хирургических представлений триангулированных 3-многообразий, хотя процедура явно не написана как алгоритм, в принципе, она должна иметь полиномиальное время выполнения по числу тетраэдров данной триангуляции 3-многообразия. ^[12]
У С. Шлеймера есть алгоритм, который создает триангулированное 3-многообразие по заданному слову (в твист-генераторах Дена ) для группы классов отображения поверхности. Трехмерное многообразие — это то, в котором это слово используется в качестве присоединяющей карты для разделения Хигора трехмерного многообразия. Алгоритм основан на концепции слоистой триангуляции .

Теория алгоритмических узлов [ править ]

Известно , что определение тривиальности узла осуществляется в классах сложности NP. ^[13] а также со-НП . ^[14]
Известно, что задача определения рода узла имеет класс сложности PSPACE . ^[13]
Существуют алгоритмы с полиномиальным временем для вычисления полинома Александера узла. ^[15]
Полином Джонса , полином ХОМФЛИ и инварианты Решетихина–Тураева представляют собой отслеживаемую таблицу с фиксированными параметрами , а полином Джонса также известен как #P-hard . ^[16] Вычисление первого коэффициента полинома HOMFLYPT и Кауфмана происходит в P . ^[17]
Аддитивная аппроксимация полинома Джонса является BQP-полной , т. е. столь же сложной, как и квантовые алгоритмы с полиномиальным временем. ^[18]
Учитывая два (ручных) узла с помощью диаграмм связей, решить, эквивалентны ли они, является ER . Это устанавливается путем сведения эквивалентности узла ( изотопии ) к эквивалентности ( гомеоморфии ) связанных с ним дополнений к узлам , которые представляют собой 3-многообразия , которые, в свою очередь, могут быть закодированы триангуляциями . Поскольку эти дополнения к узлам являются многообразиями Хакена, то используется результат о том, что проблема эквивалентности этих многообразий находится в ER. Похоже, что для этого нет хороших ссылок, эти результаты разбросаны по литературе в этой области, но хорошо известны сообществу.

гомотопия Вычислительная

Методы расчета гомотопических групп сфер .
Вычислительные методы решения систем полиномиальных уравнений .
У Брауна есть алгоритм вычисления гомотопических групп пространств, которые являются конечными комплексами Постникова : ^[19] хотя это не считается осуществимым.

гомология Вычислительная

Вычисление групп гомологии клеточных комплексов сводится к приведению граничных матриц к нормальной форме Смита . Хотя это полностью алгоритмически решенная проблема, существуют различные технические препятствия для эффективных вычислений для больших комплексов. Есть два основных препятствия. Во-первых, базовый алгоритм формы Смита имеет кубическую сложность по размеру используемой матрицы, поскольку он использует операции со строками и столбцами, что делает его непригодным для больших комплексов ячеек. Во-вторых, промежуточные матрицы, полученные в результате применения алгоритма формы Смита, заполняются, даже если начинать и заканчивать разреженными матрицами.

Эффективные и вероятностные алгоритмы нормальной формы Смита, содержащиеся в библиотеке LinBox .
Простые гомотопические сокращения для предварительной обработки вычислений гомологии, как в программном пакете Perseus .
Алгоритмы вычисления постоянной гомологии комплексов отфильтрованных , как в пакете TDAstats R. ^[20]

См. также [ править ]

Вычислимая топология (исследование топологической природы вычислений)
Вычислительная геометрия
Цифровая топология
Топологический анализ данных
Пространственно-временное рассуждение
Экспериментальная математика
Геометрическое моделирование

Ссылки [ править ]

^ Афра Дж. Зомородян, Топология вычислений , Кембридж, 2005, xi.
^ Блевинс, Энн Сайзмор; Бассетт, Даниэль С. (2020), Шрираман, Бхарат (редактор), «Топология в биологии», Справочник по математике искусств и наук , Cham: Springer International Publishing, стр. 1–23, doi : 10.1007/978 -3-319-70658-0_87-1 , ISBN 978-3-319-70658-0 , S2CID 226695484
^ Чиу, Линди (26 марта 2024 г.). «Топологи решают проблемы с размещением опросов» . Журнал Кванта . Проверено 1 апреля 2024 г.
^ Бертон, Бенджамин А. (2004). «Представляем Regina, программное обеспечение для топологии 3-многообразия» (PDF) . Экспериментальная математика . 13 (3): 267–272. дои : 10.1080/10586458.2004.10504538 . S2CID 16566807 .
^ Шлеймер, Саул (2011). «Распознавание сферы лежит в NP» (PDF) - через Уорикский университет .
^ Центнер, Рафаэль (2018). «3-сферы целочисленных гомологий допускают неприводимые представления в SL (2, C)». Математический журнал Дьюка . 167 (9): 1643–1712. arXiv : 1605.08530 . дои : 10.1215/00127094-2018-0004 . S2CID 119275434 .
^ Куперберг, Грег (2014). «Узловатость находится в NP по модулю GRH» . Достижения в математике . 256 : 493–506. arXiv : 1112.0845 . дои : 10.1016/j.aim.2014.01.007 . S2CID 12634367 .
^ Бертон, Бенджамин А.; Хайам Рубинштейн, Дж.; Тиллманн, Стефан (2009). «Додекаэдрическое пространство Вебера-Зейферта не является Хакеном». Труды Американского математического общества . 364 (2): 911–932. arXiv : 0909.4625 . дои : 10.1090/S0002-9947-2011-05419-X . S2CID 18435885 .
^ Дж.Мэннинг, Алгоритмическое обнаружение и описание гиперболических структур на 3-многообразиях с разрешимой проблемой слов, Геометрия и топология 6 (2002) 1–26
^ С.Матвеев, Алгоритмическая топология и классификация 3-многообразий, Springer-Verlag 2003.
^ Куперберг, Грег (2019). «Алгоритмический гомеоморфизм 3-многообразий как следствие геометризации». Тихоокеанский математический журнал . 301 : 189–241. arXiv : 1508.06720 . дои : 10.2140/pjm.2019.301.189 . S2CID 119298413 .
^ Константино, Франческо; Терстон, Дилан (2008). «3-многообразия эффективно связывают 4-многообразия». Журнал топологии . 1 (3): 703–745. arXiv : math/0506577 . дои : 10.1112/jtopol/jtn017 . S2CID 15119190 .
↑ Перейти обратно: Перейти обратно: ^а ^б Хасс, Джоэл ; Лагариас, Джеффри С .; Пиппенгер, Николас (1999), «Вычислительная сложность задач узлов и связей», Journal of the ACM , 46 (2): 185–211, arXiv : math/9807016 , doi : 10.1145/301970.301971 , S2CID 125854
^ Лакенби, Марк (2021), «Эффективная сертификация узловатости и нормы Терстона», Advances in Mathematics , 387 : 107796, arXiv : 1604.00290 , doi : 10.1016/j.aim.2021.107796 , S2CID 119307517
^ « Main_Page », Атлас узлов .
^ Мария, Клеман (2019). «Параметризованная сложность квантовых инвариантов». arXiv : 1910.00477 [ math.GT ].
^ Пшитицкий, Йозеф Х. (2017). «Первый коэффициент полиномов Хомфлипта и Кауфмана: доказательство Вертигана полиномиальной сложности с использованием динамического программирования». arXiv : 1707.07733 [ math.GT ].
^ Ааронов, Дорит; Джонс, Воган; Ландау, Зеф (2005). «Полиномиальный квантовый алгоритм аппроксимации полинома Джонса». arXiv : Quant-ph/0511096 .
^ Браун, Эдгар Х. (1957), «Конечная вычислимость комплексов Постникова», Annals of Mathematics (2) , 65 (1): 1–20, doi : 10.2307/1969664 , JSTOR 1969664
^ Вадхва, Рауль; Уильямсон, Дрю; Дхаван, Эндрю; Скотт, Джейкоб (2018). «TDAstats: конвейер R для вычисления постоянной гомологии при анализе топологических данных» . Журнал программного обеспечения с открытым исходным кодом . 3 (28): 860. Бибкод : 2018JOSS....3..860R . дои : 10.21105/joss.00860 . ПМЦ 7771879 . ПМИД 33381678 .

Внешние ссылки [ править ]

Книги [ править ]

Томаш Качиньский; Константин Мищайков; Мариан Мрозек (2004). Вычислительная гомология . Спрингер. ISBN 0-387-40853-3 .
Афра Дж. Зомородян (2005). Топология для вычислений . Кембридж. ISBN 0-521-83666-2 .
Вычислительная топология: введение , Герберт Эдельсбруннер, Джон Л. Харер, Книжный магазин AMS, 2010 г., ISBN 978-0-8218-4925-5

[1] Афра Дж. Зомородян, Топология вычислений , Кембридж, 2005, xi.

[2] Блевинс, Энн Сайзмор; Бассетт, Даниэль С. (2020), Шрираман, Бхарат (редактор), «Топология в биологии», Справочник по математике искусств и наук , Cham: Springer International Publishing, стр. 1–23, doi : 10.1007/978 -3-319-70658-0_87-1 , ISBN 978-3-319-70658-0 , S2CID 226695484

[3] Чиу, Линди (26 марта 2024 г.). «Топологи решают проблемы с размещением опросов» . Журнал Кванта . Проверено 1 апреля 2024 г.

[4] Бертон, Бенджамин А. (2004). «Представляем Regina, программное обеспечение для топологии 3-многообразия» (PDF) . Экспериментальная математика . 13 (3): 267–272. дои : 10.1080/10586458.2004.10504538 . S2CID 16566807 .

[5] Шлеймер, Саул (2011). «Распознавание сферы лежит в NP» (PDF) - через Уорикский университет .

[6] Центнер, Рафаэль (2018). «3-сферы целочисленных гомологий допускают неприводимые представления в SL (2, C)». Математический журнал Дьюка . 167 (9): 1643–1712. arXiv : 1605.08530 . дои : 10.1215/00127094-2018-0004 . S2CID 119275434 .

[7] Куперберг, Грег (2014). «Узловатость находится в NP по модулю GRH» . Достижения в математике . 256 : 493–506. arXiv : 1112.0845 . дои : 10.1016/j.aim.2014.01.007 . S2CID 12634367 .

[8] Бертон, Бенджамин А.; Хайам Рубинштейн, Дж.; Тиллманн, Стефан (2009). «Додекаэдрическое пространство Вебера-Зейферта не является Хакеном». Труды Американского математического общества . 364 (2): 911–932. arXiv : 0909.4625 . дои : 10.1090/S0002-9947-2011-05419-X . S2CID 18435885 .

[9] Дж.Мэннинг, Алгоритмическое обнаружение и описание гиперболических структур на 3-многообразиях с разрешимой проблемой слов, Геометрия и топология 6 (2002) 1–26

[10] С.Матвеев, Алгоритмическая топология и классификация 3-многообразий, Springer-Verlag 2003.

[11] Куперберг, Грег (2019). «Алгоритмический гомеоморфизм 3-многообразий как следствие геометризации». Тихоокеанский математический журнал . 301 : 189–241. arXiv : 1508.06720 . дои : 10.2140/pjm.2019.301.189 . S2CID 119298413 .

[12] Константино, Франческо; Терстон, Дилан (2008). «3-многообразия эффективно связывают 4-многообразия». Журнал топологии . 1 (3): 703–745. arXiv : math/0506577 . дои : 10.1112/jtopol/jtn017 . S2CID 15119190 .

[HLP-13] Перейти обратно: Перейти обратно: ^а ^б Хасс, Джоэл ; Лагариас, Джеффри С .; Пиппенгер, Николас (1999), «Вычислительная сложность задач узлов и связей», Journal of the ACM , 46 (2): 185–211, arXiv : math/9807016 , doi : 10.1145/301970.301971 , S2CID 125854

[14] Лакенби, Марк (2021), «Эффективная сертификация узловатости и нормы Терстона», Advances in Mathematics , 387 : 107796, arXiv : 1604.00290 , doi : 10.1016/j.aim.2021.107796 , S2CID 119307517

[15] « Main_Page », Атлас узлов .

[16] Мария, Клеман (2019). «Параметризованная сложность квантовых инвариантов». arXiv : 1910.00477 [ math.GT ].

[17] Пшитицкий, Йозеф Х. (2017). «Первый коэффициент полиномов Хомфлипта и Кауфмана: доказательство Вертигана полиномиальной сложности с использованием динамического программирования». arXiv : 1707.07733 [ math.GT ].

[18] Ааронов, Дорит; Джонс, Воган; Ландау, Зеф (2005). «Полиномиальный квантовый алгоритм аппроксимации полинома Джонса». arXiv : Quant-ph/0511096 .

[19] Браун, Эдгар Х. (1957), «Конечная вычислимость комплексов Постникова», Annals of Mathematics (2) , 65 (1): 1–20, doi : 10.2307/1969664 , JSTOR 1969664

[20] Вадхва, Рауль; Уильямсон, Дрю; Дхаван, Эндрю; Скотт, Джейкоб (2018). «TDAstats: конвейер R для вычисления постоянной гомологии при анализе топологических данных» . Журнал программного обеспечения с открытым исходным кодом . 3 (28): 860. Бибкод : 2018JOSS....3..860R . дои : 10.21105/joss.00860 . ПМЦ 7771879 . ПМИД 33381678 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]