В ИНФОРМАТИКЕ ПАЛ БАРЬЕР 1962 ГОДА

Гамильтонов цикл — это замкнутый маршрут по сети, который посещает каждую точку ровно один раз и возвращается в начало. В ориентированной сети каждая связь — это стрелка, по которой можно пройти только в одну сторону, как по улице с односторонним движением. Взвешенный вариант этой задачи — асимметричная задача коммивояжёра.

Определить, существует ли такой цикл, — хрестоматийная трудная задача. В 1962 году Ричард Беллман и независимо от него Майкл Хелд и Ричард Карп предложили алгоритмы динамического программирования, решающие её примерно за время 2ⁿ для сети из n точек (с точностью до множителей, растущих лишь полиномиально). Более шестидесяти лет никому не удавалось принципиально улучшить этот результат для произвольных ориентированных сетей.

Неориентированный родственник пал раньше

Для сетей с двусторонними связями Андреас Бьёрклунд преодолел барьер в 2014 году с помощью рандомизированного алгоритма, работающего за 1,657ⁿ; по данным статьи, эта работа принесла ему премию Нероуда EATCS–IPEC 2016 года. Это по-прежнему самый быстрый известный алгоритм для произвольных неориентированных сетей. Для ориентированных прогресс был лишь в частных случаях — для двудольных сетей, для сетей с малым числом связей у каждой точки — или при опоре на недоказанную гипотезу, гипотезу Штрассена об асимптотическом ранге.

Новая оценка

Томохиро Коана из Токийского университета и Со Кумабэ из токийской компании CyberAgent теперь предлагают рандомизированный алгоритм, решающий ориентированную задачу за время

O((375/196)ⁿ) = O(1,9133ⁿ)**.

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

Счёт на чёт и нечет

Трудность здесь тонкая. Считать циклы по модулю 2 — то есть знать лишь, чётно их число или нечётно, — уже умели быстрее чем за 2ⁿ. Но чётное ненулевое число циклов выглядит в точности как ноль. Классическое решение — присвоить связям случайные веса, чтобы при каком-то суммарном весе решение стало единственным (лемма об изоляции); однако быстрый метод подсчёта чётности не умел работать с весами.

Рецепт авторов простыми словами:

1. Угадать одну стрелку цикла и искать вместо него путь через все точки от одного конца этой стрелки до другого.
2. Удалить каждую стрелку случайным образом с вероятностью 1/50.
3. В каждой точке создать три группы входящих стрелок и скопировать каждую уцелевшую стрелку в случайный непустой набор групп.
4. Если маршрут существует, то с вероятностью не меньше (49/50)ⁿ⁻¹ можно выбрать по одной группе в каждой точке так, чтобы число допустимых путей было нечётным.
5. Присвоить случайный вес каждой группе, а не каждой стрелке. Теперь трюк с изоляцией работает, и хватает примерно (50/49)ⁿ повторений.
6. Каждое повторение вычисляет чётность числа путей для каждого суммарного веса за время (15/8)ⁿ, используя суммы определителей матриц, предложенные Бьёрклундом, Каски и Коутисом, и случайную «линеаризацию», которую применяли также Арвинд и Гурусвами.

Перемножаем: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1,9133ⁿ.

Доказательство, сгенерированное машиной

Статья завершается заявлением о генеративном ИИ: ChatGPT 6 Astra сгенерировал доказательство основной теоремы и помог составить рукопись. Авторы сформулировали промежуточные утверждения, дающие комбинаторное прочтение исходного решения модели, затем всё проверили и доработали и берут на себя полную ответственность.

Результат теоретический — никакая программа не запускалась, — а алгоритм рандомизированный, с небольшой вероятностью ошибки в любую сторону. Между 1,9133 для улиц с односторонним движением и 1,657 для двусторонних остаётся широкий открытый разрыв.