Задача розв'язування

Задача розв'язування — задача алгоритмічного розпізнавання тривіального вузла якщо задано певне подання вузла, тобто діаграма вузла. Існує кілька видів алгоритмів розв'язування. Основна невирішена проблема — чи можна розв'язати задачу за поліноміальний час, тобто, чи належить задача до класу складності 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]. Бар-Натан не дає строгого аналізу свого алгоритму, але евристичний передбачає, що алгоритм експоненціальний від шляхової ширини графу діаграми перетинів, яка, в свою чергу, не більша від квадратного кореня з числа перетинів (з деяким коефіцієнтом).

Складність цих алгоритмів активно вивчається.

Див. також

Примітки
  1. Hass, Lagarias, Pippenger, 1999.
  2. Hara, Tani, Yamamoto, 2005.
  3. Згадано як «часткове повідомлення» [15] у списку посилань статті Куперберга (Kuperberg, 2014).
  4. Kuperberg, 2014.
  5. Kawarabayashi, Kreutzer, Mohar, 2010.
  6. Ladd, Kavraki, 2004.
  7. Burton, 2011a.
  8. Birman, Hirsch, 1998.
  9. Lackenby, 2015.
  10. Mijatović, 2005.
  11. Burton, 2011b.
  12. Manolescu, Ozsváth, Sarkar, 2009.
  13. Kronheimer, Mrowka, 2011.
  14. Bar-Natan, 2007.

Література

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.