Hacker News Digest

Математики опровергли простой метод измерения сложности узлов, предложенный ещё в 1876 году Питером Тейтом. Он предполагал, что «заузленность» можно измерить минимальным числом пересечений, которые нужно перевернуть, чтобы развязать узел. Этот параметр, известный как unknotting number, долгое время считался интуитивно понятным инструментом для классификации узлов.

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

• Обсуждается нетипичное поведение узлов, в частности, невозможность простого сложения их "чисел развязывания" при комбинировании.
• Высказывается гипотеза о существовании "отрицательного" числа развязывания для некоторых узлов, чтобы объяснить расхождения в расчетах.
• Уточняется, что проблема возникает из-за непредсказуемости изменения пересечений при соединении узлов.
• Отмечается, что для торических узлов все пересечения можно изобразить как положительные или отрицательные, что усложняет теорию.
• Обсуждается возможная связь концепции с другими математическими областями, такими как мнимые или сюрреальные числа.

Содержимое PDF-файла представляет собой бинарные данные, которые нельзя напрямую интерпретировать как текст. В представленном фрагменте — это служебные структуры PDF (объекты, потоки, метаданные), а не читаемый текст документа.
Перевод и сокращение невозможны, поскольку отсутствует осмысленный текстовый контент.

• Брукс по-прежнему прав: основная трудность — «существенная сложность» предмета, а не инструменты.
• За 40 лет не появилось ни одного «серебряного пули», дающего 10× прирост продуктивности.
• Экосистемы (Python, AWS и др.) снизили accidental complexity, но добавили новую через зависимости и «слоёный пирог».
• LLM и ИИ ускоряют рутину, но не решают существенную сложность и не умеют формулировать требования.
• Культура SWE изменилась: скорость вытеснила ответственность, код пишут «на скорую руку» и быстро забывают.

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

Это особенно заметно в культовой задаче информатики — поиске кратчайших путей от одной вершины графа до всех остальных. Интуитивно проще сначала находить ближайшие цели, затем более дальние. Но для этого нужно постоянно определять, какая вершина ближе, то есть фактически сортировать по расстоянию. Возникает «барьер сортировки»: алгоритм, зависящий от сортировки, не может быть быстрее, чем сама сортировка.

Команда исследователей предложила новый алгоритм, который обходится без сортировки и работает быстрее всех «сортирующих» методов, преодолев сорокалетний барьер. Роберт Тарьян назвал результат поразительным.

Графы описывают вершины и ребра с весами (длина, время и т.п.). Задача: по данному источнику найти кратчайшие пути до всех вершин. Алгоритм Дейкстры (1956) идет «волной» наружу: зная оптимальные пути к ближайшим, находит пути к дальним. Но конечный результат — упорядоченный набор кратчайших расстояний, и потому скорость ограничена сортировкой. В 1984 году Тарьян с соавтором улучшили Дейкстру до этого предела: чтобы ускориться дальше, нужно избегать сортировки.

В конце 1990-х — начале 2000-х Торуп и другие обошли барьер для частных случаев, вводя ограничения на веса. Обобщить техники на произвольные веса не удавалось, и прогресс застопорился. Ран Дуань не согласился с пессимизмом и стремился сломать барьер для всех графов — и прошлой осенью добился цели.

Идея Дуани (созревшая к 2021 году): вместо того чтобы на каждом шаге сканировать всю «границу» уже исследованной области, как делает Дейкстра (что со временем замедляет ход), группировать соседние граничные вершины в кластеры и рассматривать по одному представителю из каждого. Это уменьшает число кандидатов и может вести не к ближайшей вершине — значит, зависимость от сортировки исчезает. Главная трудность — доказать, что кластеризация действительно ускоряет процесс на каждом шаге и в сумме.

За следующий год Дуань проработал идею и к осени 2022-го был уверен, что технические барьеры преодолимы.

• Обсуждение вокруг нового алгоритма SSSP с детерминированной сложностью O(m log^(2/3) n), который улучшает Дейкстру на разреженных графах; ссылку дали на arXiv: 2504.17033.
• Участники отмечают, что выигрыш зависит от структуры графа: для дорожных сетей обычно m ≈ c·n (c ~ 4–6 для ориентированных), что даёт O(n log^(2/3) n); для очень плотных графов (m ~ n^2) преимущество может исчезать.
• Возникают вопросы о сравнении логарифмических степеней, применимости к задачам вроде TSP с почти полными графами, и сохранении гарантии глобального минимума как у Дейкстры.
• Некоторые считают алгоритм сложнее Дейкстры, но отмечают теоретическую значимость прорыва и отсутствие «фancy math», что делает результат удивительным.
• Обсуждают возможные гибриды с рандомизацией и практическое влияние на реальные графы (улицы, геймдев).
• Есть скепсис о «позднем открытии» и комментарии про то, что практики могли бы дойти до подобных идей, но не оформляют их академически.
• Вспоминают вклад классиков (Тарjan и др.) и проводят аналогию с TimSort: практичная оптимизация поверх классики.