Задача развязывания — задача алгоритмического распознавания тривиального узла если задано некоторое представление узла, то есть диаграмма узла. Существует несколько видов алгоритмов развязывания. Основная нерешённая проблема — можно ли решить задачу за полиномиальное время, то есть, принадлежит ли задача классу сложности P.
Первые шаги в определении вычислительной сложности были предприняты в сторону доказательства, что задача принадлежит более сложным классам сложности, содержащим класс P. С использованием нормальных поверхностей[англ.] для описания поверхностей Зейферта заданного узла Хасс, Лагариас и Пиппенжер[1] показали, что задача развязывания принадлежит классу сложности NP. Хара, Тани и Ямамото[2] заявили, что развязывание принадлежит классу AM ∩ co-AM[англ.]. Позднее, однако, они отозвали своё заявление[3]. В 2011 Грег Куперберг[англ.] доказал, что (в предположении верности обобщённой гипотезы Римана) задача развязывания принадлежит классу co-NP[4].
Задача развязывания имеет ту же вычислительную сложность, что и проверка, является ли вложение неориентированного графа в евклидово пространствонезацепленным[5].
Узел Отиаи, содержащий 139 вершин, например, был сперва развязан с помощью компьютера за 108 часов, но это время впоследствии сокращено до 10 минут[6]
Алгоритмы развязывания
Некоторые алгоритмы решения задачи развязывания основываются на теории Хакенанормальных поверхностей[англ.]:
Алгоритм Хакена использует теорию нормальных поверхностей для поиска диска, граница которого заузлена. Хакен изначально использовал этот алгоритм, чтобы показать, что задача развязывания разрешима, но он не анализировал вычислительную сложность алгоритма детально.
Хасс, Лагариас и Пиппенджер показали, что множество всех нормальных поверхностей можно представить как целые точки в многогранном конусе и что поверхность, свидетельствующая о возможности развязывания кривой (если таковая существует), может быть всегда найдена на одном из крайних лучей этого конуса. Таким образом, методы перечисления вершин[англ.] могут быть использованы для перечисления всех крайних лучей и проверки, не являются ли они заузлёнными границами диска. Хасс, Лагариас и Пиппенджер использовали этот метод, чтобы показать, что нахождение развязывания принадлежит классу NP. Позднее исследователи, такие как Бартон[7] улучшили их анализ, показав, что этот алгоритм может быть полезен, имея невысокого порядка экспоненциальную сложность (как функцию от числа пересечений).
Алгоритм Бирмана и Хирша[8] использует расслоение кос[англ.], несколько другую структуру, отличную от нормальной поверхности. Однако для анализа их поведения они вернулись к теории нормальных поверхностей.
Другие подходы:
Число движений Рейдемейстера, необходимых для приведения диаграммы тривиального узла к стандартному виду не более чем полиномиально от числа пересечений[9]. Поэтому, полный поиск всех движений Рейдемейстера может обнаружить тривиальность узла за экспоненциальное время.
Похожим образом любые две триангуляризации одного и того же дополнения узла могут быть соединены последовательностью движений Пачнера длиной не больше двойного экспоненциала от числа пересечений[10]. Таким образом, можно определить, является ли узел тривиальным путём проверки последовательностей движений Пачнера этой длины, начиная с дополнения заданного узла, а затем проверки, нельзя ли какое-либо из этих движений преобразовать в стандартную триануляцию полного тора. Время этого метода должно бы быть трижды экспоненциальным, однако эксперименты показывают, что эти границы очень пессимистичны и нужно куда меньше движений Пачнера[11].
Остаточная конечностьгруппы узла (которая следует из геометризации многообразий Хакена) даёт алгоритм — проверяем, не содержит ли группа нециклическую конечную факторгруппу. Эта идея используется в доказательстве Куперберга, что задача развязывания входит в класс co-NP.
Гомология Флоера[англ.] узла определяет род узла, который равен 0 тогда и только тогда, когда узел тривиален. Комбинаторная версия гомологии Флоера узла может быть вычислена[12].
Гомология Хованова[англ.] определяет тривиальность узла согласно результатам Кронхеймера[англ.] и Мровки[англ.][13]. Сложность гомологии Хованова по меньшей мере такая же как у #P-трудной задачи вычисления полинома Джонса, но он может быть вычислен с помощью алгоритма и программы Бар-Натана[14]. Бар-Натан не даёт строгого анализа своего алгоритма, но эвристически предполагает, что алгоритм экспоненциален от путевой ширины графа диаграммы пересечений, которая, в свою очередь, не больше квадратного корня от числа пересечений (с некоторым коэффициентом).
Изучение сложности этих алгоритмов активно продолжается.
Dror Bar-Natan. Fast Khovanov homology computations // Journal of Knot Theory and Its Ramifications. — 2007. — Т. 16, вып. 3. — С. 243—255. — doi:10.1142/S0218216507005294. — arXiv:math.GT/0606318.
Joan S. Birman, Michael Hirsch. A new algorithm for recognizing the unknot // Geometry and Topology. — 1998. — Т. 2. — С. 178—220. — doi:10.2140/gt.1998.2.175.
Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. The number of Reidemeister moves needed for unknotting // Journal of the American Mathematical Society. — 2001. — Т. 14, вып. 2. — С. 399—428. — doi:10.1090/S0894-0347-01-00358-7.
Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar. Proc. ACM Symposium on Computational Geometry (SoCG '10). — 2010. — С. 97—106. — doi:10.1145/1810959.1810975.
Peter Kronheimer, Tomasz Mrowka. Khovanov homology is an unknot-detector // Publications Mathématiques de l'IHÉS. — 2011. — Т. 113, вып. 1. — С. 97—208. — doi:10.1007/s10240-010-0030-y. — arXiv:1005.4346.
Andrew M. Ladd, Lydia E. Kavraki. Algorithmic Foundations of Robotics V / Jean-Daniel Boissonnat, Joel Burdick, Ken Goldberg, Seth Hutchinson. — Springer, 2004. — Т. 7. — С. 7—23. — (Springer Tracts in Advanced Robotics). — doi:10.1007/978-3-540-45058-0_2.
Aleksandar Mijatović. Simplical structures of knot complements // Mathematical Research Letters. — 2005. — Т. 12, вып. 6. — С. 843—856. — doi:10.4310/mrl.2005.v12.n6.a6. — arXiv:math/0306117.
Зада́ча выполни́мости бу́левых фо́рмул — важная для теории вычислительной сложности алгоритмическая задача.
В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число , такое, что время работы алгоритма для всех входов длины не превосходит , то временную сложность данного алгоритма можно асимптотически оценить как .
Тривиальный узел — геометрический узел, объемлюще-изотопный стандартному вложению окружности в трёхмерную сферу, а также объемлюще-изотопический класс такого геометрического узла.
В математической теории узлов движением (преобразованием) Рейдемейстера называют одно из трёх локальных движений на диаграмме зацепления. В 1927 году Джеймс Александер и Бриггс, а также независимо от них Курт Рейдемейстер, показали, что две диаграммы, относящиеся к одному и тому же узлу, с точностью до плоской изотопии могут быть преобразованы одна в другую с помощью последовательного применения одного из трёх движений Рейдемейстера.
В теории сложности, QMA — это квантовый аналог NP в классической теории сложности и аналог MA в вероятностной. Он связан с BQP также, как NP связан с P, или MA связан с BPP.
В теории вычислительной сложности теорема PCP утверждает, что любое решение задачи принятия решения в классе сложности NP имеет вероятностно проверяемое доказательство постоянной сложности запроса и логарифмической сложности случайности.
Многочлен Александера — это инвариант узла, который сопоставляет многочлен с целыми коэффициентами узлу любого типа. Джеймс Александер обнаружил его, первый многочлен узла, в 1923. В 1969 Джон Конвей представил версию этого многочлена, ныне носящую название многочлен Александера — Конвея. Этот многочлен можно вычислить с помощью скейн-соотношения, хотя важность этого не была осознана до открытия полинома Джонса в 1984. Вскоре после доработки Конвеем многочлена Александера стало понятно, что похожее скейн-cоотношение было и в статье Александера для его многочлена.
В теории узлов число пересечений узла — это наименьшее число пересечений на любой диаграмме узла. Число пересечений является инвариантом узла.
Зацепление кратности — вложение несвязной суммы экземпляров окружности в или .
В теории узлов обратимый узел — это узел, который может быть непрерывной деформацией переведён в себя, но с обратной ориентацией. Необратимый узел — это любой узел, который не имеет такого свойства. Обратимость узла является инвариантом узла. Обратимое зацепление — это зацепление с таким же свойством.
Число развязывания в теории узлов — один из важных инвариантов узла, минимальное число переключения мостов, то есть число переходов сквозь себя, после чего узел развязывается.
Незацепленное вложение графа — вложение неориентированного графа в евклидово пространство, при котором никакие два цикла графа не имеют ненулевой коэффициент зацепления. Плоское вложение — вложение, при котором любой цикл является границей топологического круга, внутренность которого не зацеплена с графом. Вложимый без зацеплений граф — граф, имеющий незацепленное или плоское вложение. Эти графы образуют трёхмерный аналог планарным графам. В противоположность, существенно зацепленный граф — это граф, не имеющий незацепленного вложения.
В теории графов доминирующее множество для графа G = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D. Число доминирования γ(G) — это число вершин в наименьшем доминирующем множестве G.
Гипотеза Келлера — выдвинутая Отт-Генрихом Келлером гипотеза о том, что в любой мозаике в евклидовом пространстве, состоящей из одинаковых гиперкубов, найдутся два куба, соприкасающиеся грань-к-грани. Например, как показано на рисунке, в любой мозаике на плоскости из одинаковых квадратов какие-то два квадрата должны соприкасаться ребро-к-ребру. Перрон доказал, что это верно в размерностях до 6; Бракензик с соавторами доказали верность гипотезы для размерности 7. Однако для бо́льших размерностей это неверно, как показали Лагариас и Шор для размерностей 10 и выше, Макей для размерностей 8 и выше, для чего использовали переформулировку задачи в терминах кликового числа некоторых графов, известных теперь как графы Келлера.
Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является NP-трудной и не может быть решена за полиномиальное время для произвольных графов, если только не P = NP. Принадлежность более тяжелому классу сложности также означает, что задачу трудно аппроксимировать. Однако задача решается за линейное время на ориентированных ациклических графах, которые имеют важное применение в задачах нахождения критического пути в задачах планирования.
Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H. Задача поиска изоморфного подграфа является обобщением как задачи о максимальной клике, так и задачи о проверке, не содержит ли граф гамильтонов цикл, а потому является NP-полной. Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время.
Гипотеза об экспоненциальном времени — это недоказанное допущение о вычислительной сложности, которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT не может быть решена за субэкспоненциальное время в худшем случае. Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты по сложности в том смысле, что если одна из них имеет алгоритм экспоненциального времени, то все они имеют алгоритмы такой же сложности.
Задачи теории решёток — это класс задач оптимизации на решётках. Гипотетическая плохая разрешимость таких задач является центральным местом для построения стойких криптосистем на решётках. Для приложений в таких криптосистемах обычно рассматриваются решётки на векторных пространствах или свободных модулях.
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе. Обе задачи NP-полны.
Сечение нечётных циклов неориентированного графа — это набор вершин графа, который имеет непустое пресечение с любым нечётным циклом в графе. Удаление вершин сечения нечётных циклов из графа оставляет двудольный граф в качестве порождённого подграфа.
Эта страница основана на статье Википедии. Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия. Изображения, видео и звуки доступны по их собственным лицензиям.
