Информатика и ИИПрепринтТеория3 мин чтения

СОРТИРОВКА С ЗАПРЕЩЁННЫМИ СРАВНЕНИЯМИ — ПОЧТИ ТАК ЖЕ БЫСТРО

Чтобы упорядочить n элементов, сравнивая их попарно, необходимо и достаточно около n log n сравнений. Но это предполагает, что сравнить можно любые два элемента.

Часто это не так. Авторы заимствуют пример из статьи 2011 года: на одну вакансию претендуют несколько кандидатов, у каждого есть рекомендатели. Двух кандидатов можно сравнить, только если какой-то рекомендатель знает обоих. Разрешённые сравнения образуют сеть — граф: каждый элемент — точка, каждое допустимое сравнение — связь. Истинный порядок скрыт, но граф гарантированно его содержит — в виде пути, который соединяет каждый элемент со следующим. Вопрос: сколько сравнений нужно, чтобы восстановить порядок? Это и есть обобщённая сортировка (generalized sorting).

Почему обычные приёмы не работают

Классические алгоритмы опираются на свободу выбора. QuickSort выбирает «опорный элемент» (pivot) и сравнивает его с большинством остальных элементов, но в произвольном графе может не оказаться элемента, связанного с большинством других. MergeSort делит элементы на группы и сортирует каждую, но группу может оказаться невозможно отсортировать саму по себе: два элемента, соседние в итоговом порядке, не обязаны быть связаны внутри неё. Если смотреть глубже, в обычной сортировке всегда есть доступное сравнение, которое исключает заметную долю возможных порядков; при ограниченных сравнениях такого может не быть.

Прогресс шёл медленно. В 2011 году Чжии Хуан, Сампат Каннан и Санджив Ханна нашли метод, которому требовалось около n¹·⁵ сравнений с точностью до логарифмических множителей, и для произвольных графов эта оценка с тех пор так и держалась. Они даже задавались вопросом, не может ли задача быть принципиально труднее обычной сортировки и требовать n в степени больше 1.

Сначала предсказать, потом исправить

Санджив Ханна из Нью-Йоркского университета, Аарон Путтерман из Гарвардского университета и Цзюнькай Сун, тоже из Нью-Йоркского университета, теперь отвечают на этот вопрос: нет. Их рандомизированный алгоритм сортирует в среднем примерно за n log⁴ n сравнений на любом графе — всего на несколько логарифмических множителей больше, чем обычная сортировка. И, как они пишут, он «относительно прост». Однако выигрыш теоретический: константы в доказательстве огромны (множители вроде 2³²), поэтому преимущество проявляется лишь при очень больших n.

В его основе — известный результат: если кто-то даёт вам догадку о направлении каждой связи, ошибочную для w из них, порядок можно восстановить примерно за n log n + w сравнений. Так задача сводится к тому, чтобы получить догадку с малым числом ошибок, потратив мало сравнений. Ключевые шаги:

  • Грубая первая догадка. Сравнить случайную выборку связанных пар и выбрать любой порядок, согласующийся с ответами. Ошибок в нём много, но не слишком.
  • Изолировать ошибки, а не исправлять их. Вместо того чтобы исправлять неверные догадки, алгоритм находит части графа, где ошибки встречаются чаще среднего, и откладывает их в сторону. Каждый раунд сокращает оставшиеся ошибки в среднем в четыре раза.
  • Вернуться позже. Отложенные связи обрабатываются на одной из следующих фаз. Каждая фаза решает как минимум половину ещё не обработанных связей, так что для миллиона связей хватает примерно двадцати фаз.

Доказательство, найденное с помощью машин

Раздел статьи об использовании ИИ необычно подробен. В нём сказано, что ChatGPT 6-Astra «был незаменим для доказательства улучшенных оценок». Сначала модель нашла алгоритм примерно с n¹·³³ сравнений, а затем застопорилась. Авторы довели его до n¹·²; затем, после десятков запросов в течение нескольких недель, модели находили последовательные улучшения — n^(10/9), n^(17/16), n^(19/18), — пока не пришли к почти линейному алгоритму. Авторы добавляют, что неясно, был ли их собственный промежуточный шаг необходим для этого итогового открытия.

Что остаётся открытым

Результат учитывает сравнения, а не время вычислений: в нынешнем виде алгоритм не работает за полиномиальное время, тогда как метод 2011 года работал. Авторы перечисляют три открытых вопроса: можно ли убрать оставшиеся логарифмические множители, может ли алгоритм без случайности справиться не хуже и может ли эффективный алгоритм достичь того же числа сравнений — или хотя бы вообще превзойти n¹·⁵.