Математик совершил прорыв в решении проблемы узлов 100-летней давности

Теперь развязать узел стало легче. Одной из самых больших проблем в математических исследованиях узлов является понимание разницы между реальным узлом и веревкой, которую можно разбить на петли. Новые алгоритмы могут найти это “невозможное” быстрее, чем любой предыдущий алгоритм. Это может быть полезно для изучения запутывания ДНК и механики звездной жидкости.

Математически узел определяется как замкнутая криволинейная веревка, концы которой связаны вместе, и ее нельзя разбить на простые петли. Каким бы сложным и запутанным это ни казалось, все, что может быть решено в простом цикле, называется невозможным. “Ноль — это не узел, так же как ноль — это не число”, — говорит Марк Денис из Бирмингемского университета, Великобритания.

В течение примерно 100 лет математики изо всех сил пытались найти алгоритм, позволяющий определить, действительно ли узел неизвестен. Алан Тьюринг, математик-первопроходец и специалист по компьютерам, написал об этом в своей последней диссертации 1954 года. Об этом написано в этой статье. В настоящее время Марк Лакенби из Оксфордского университета в Великобритании разработал алгоритм, который может провести это различие быстрее, чем любой другой алгоритм.

“Мы сломали все провода, кабели, шнуры для наушников и т. д. На протяжении всей нашей жизни, поэтому открытие неизвестного может показаться интуитивным, но математически это более абстрактно, чем геометрия. Проблема выше, чем сказал Деннис. Существует график узлов, который необходимо усложнить, прежде чем его можно будет упростить, и компьютер знает, когда это сделать. Я не очень хорошо разбираюсь в этом”, — сказал он.

Сложность конкретного узла зависит от количества узлов в узле. Пересечение — это точка, в которой одна часть провода находится выше или ниже другой, и вы можете манипулировать переплетенными частями, чтобы избежать поперечного сечения.

“Вы можете подумать, что это не сложная проблема, но проблема в том, что, когда вы начинаете думать о том, как ваш компьютер на самом деле определяет такую проблему, вы понимаете, что у вас нет правильных инструментов для этого“, — добавляет Лакенби.

Другие математики придумали алгоритм, который может проверить, связано ли конкретное сплетение, но для каждого прохода требуется вдвое больше времени, чтобы выяснить, неизвестно ли сплетение.

Лакенби разработал первый алгоритм, который был быстрее этого. Его работа основана на определении каждого узла как ребра, представляющего трехмерную форму.

“Я могу представить себе круг, который находится не на плоскости, а на границе диска”, — сказал Лэзенби. “Или вы можете представить, как берете лист бумаги и склеиваете их в петлю с небольшим поворотом, а граница этого листа бумаги представляет собой узел”.

Если форму, соответствующую кнопке, можно обработать и уменьшить до блюдца, кнопка будет практически невидима. Определение того, неизвестен ли узел, имеет широкий спектр применений: от изучения того, как ДНК соединяется внутри клеток, до понимания колец плазмы, из которых состоит звезда. Поэтому более быстрые алгоритмы могут быть очень полезны.

Автор записи
. Top.Mail.Ru