КОГДА 1 СТОИТ ДОРОЖЕ 0, СЖАТИЕ СТАНОВИТСЯ ТРУДНЫМ

Чтобы хранить или передавать текст компактно, каждому символу дают слово из нулей и единиц — короткое для частых символов и более длинное для редких. Слова должны образовывать префиксный код: ни одно слово не может быть началом другого. {0, 10, 11} подходит; {0, 01, 11} — нет, потому что 01 начинается с 0. С префиксным кодом длинную строку битов можно снова разрезать на слова без всяких разделителей.

Наилучший такой код — с наименьшей средней длиной — был найден в 1952 году Д. А. Хаффманом (D. A. Huffman): это простой жадный рецепт, который работает быстро.

Когда у букв есть цена

Рецепт Хаффмана предполагает, что 0 и 1 стоят одинаково. Допустим, это не так: 1 дольше передаётся или занимает больше места при хранении. Тогда стоимость каждого слова равна сумме стоимостей его букв, и состав слова важен не меньше, чем его длина. Например, при стоимостях 1 и 3 слова 00 и 01 одинаковой длины, но стоят 2 и 4.

У этого варианта задачи долгая история. В 1961 году она была записана Р. М. Карпом (R. M. Karp) как задача целочисленного программирования. Позднее были найдены точные эффективные алгоритмы для любой фиксированной пары целочисленных стоимостей, а также схема приближения, позволяющая подойти к оптимуму сколь угодно близко. Но когда сами стоимости входят во входные данные, никто не знал, насколько трудна задача. Ещё в 2021 году она числилась среди открытых.

Ответ: NP-полнота

Л. Сунил Чандран (L. Sunil Chandran) из Индийского института науки в Бенгалуру и Ришикеш Гаджала (Rishikesh Gajjala) из Pramaana Labs теперь доказывают, что решить, существует ли код стоимостью не более K, — NP-полная задача, даже когда две стоимости — последовательные целые числа M и M + 1. Специалисты по информатике называют задачу NP-полной, когда она так же трудна, как целое семейство классических задач: быстрый общий метод для одной из них дал бы такой метод для всех, а ни одного такого метода не известно. Поэтому поиск самого дешёвого кода — NP-трудная задача.

Противоречия с быстрыми алгоритмами для фиксированных стоимостей здесь нет. В доказательстве M растёт вместе с входными данными; для любой пары стоимостей, зафиксированной заранее, эти алгоритмы по-прежнему применимы.

Головоломка, спрятанная в кодовом дереве

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

Любой префиксный код — это дерево: 0 ведёт влево, 1 — вправо. Слово глубины d, содержащее z единиц, стоит M × d + z, когда буквы стоят M и M + 1. Глубина задаёт основную часть стоимости, а число единиц — малую.
Авторы придумывают новую промежуточную задачу: фиксируют, сколько листьев у дерева на каждой глубине, и оценивают, где именно эти листья расположены. Они показывают, что дешёвое дерево, вырастая уровень за уровнем, должно выполнять небольшую программу, которая проверяет выбранные точки одну за другой, копирует каждый выбор и проверяет каждую связь. Любое отклонение от неё обходится как минимум на одну единицу дороже; каждая выбранная точка экономит ровно одну.
Наконец, частоты подбираются так, чтобы каждый символ был вынужден оказаться на нужной глубине, и оценка становится равна стоимости кодирования плюс фиксированная величина.

Небольшой пример из статьи показывает, насколько тонко устроены стоимости. У трёх символов частоты 20, 12 и 9, а буквы стоят 83 и 84. Код (0, 10, 11) стоит 5176. Код (1, 00, 01) стоит 5175: выгоднее отдать дорогую букву самому частому символу, потому что тогда в двух других словах меньше единиц.

Где прячется трудность

Второй результат указывает, где трудность скрыта внутри обычного кодирования. Рецепт Хаффмана быстро находит наименьшую среднюю длину. Но среди всех кодов, достигающих этой длины, выбрать код с наименьшим числом единиц с учётом частот — тоже NP-полная задача.

Остаются вопросы: остаётся ли задача трудной, когда все числа малы (так называемая сильная NP-трудность), и существует ли быстрая схема, приближающая оптимум с любой точностью, время работы которой также растёт с этой точностью разумно.

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

В статье сказано, как оно было получено. Сначала авторы попросили Codex от OpenAI доказать трудность более общей задачи, затем — распространить доказательство на недвоичные и, наконец, на двоичные коды. Codex внёс вклад в стратегию сведения и её математическую разработку; он также помогал с написанием текста, проверкой рассуждений и построением примеров. Авторы направляли работу, запрашивали исправления и упрощения, существенно переписали изложение и несут ответственность за окончательные формулировки и доказательства. Как и любой препринт, работа ещё не прошла рецензирование.