Левин: универсальные задачи перебора

Две страницы

Л. А. Левин, «Универсальные задачи перебора», журнал «Проблемы передачи информации», том 9, выпуск 3, 1973 год, страницы 115–116.

Две страницы. Шесть задач, объявленных универсальными. Никаких ссылок на Кука — он о нём не знал; никаких ссылок на Карпа — их работы шли параллельно и о существовании друг друга авторы узнали позже.

Теорема, которую сегодня во всём мире называют теоремой Кука — Левина, в СССР была доказана независимо и напечатана так коротко, что западные читатели, добравшись до перевода, сначала не поверили, что там всё есть.

«Перебор» — русское слово в этой истории

Вопрос был поставлен в СССР рано и в собственных словах.

Ещё в конце 1950-х на семинарах КолмогороваАндрей Николаевич Колмогороврусский и советский математик · 1903–1987Дал вероятности аксиомы, турбулентности — закон, сложности — определение, а школьной математике в СССР — программу, по которой учились миллионы. обсуждали проблему перебора: можно ли для переборных задач — тех, где ответ ищется просмотром экспоненциально многих вариантов, — обойтись без просмотра? В 1959 году С. В. Яблонский напечатал работу «О невозможности элиминации перебора при решении некоторых задач теории функций алгебры логики», где утверждал, что для задачи о минимальных схемах перебор неустраним. Утверждение относилось к узко очерченному классу алгоритмов, и как ответ на общий вопрос его не приняли — но само слово прижилось, и целое направление в СССР называлось «проблема перебора».

Терминологическая разница показательна. На Западе спрашивали: принадлежит ли задача классу P? В Москве: можно ли устранить перебор? Второе — тот же вопрос, но заданный со стороны действия, а не со стороны классификации.

Поиск, а не распознавание

Главное отличие работы Левина от работы Кука — в постановке.

Кук рассматривает задачи распознавания: на вход формула, на выход «да» или «нет». Левин рассматривает задачи поиска: на вход условие, на выход — сам объект, если он есть.

Практика всегда хочет второго. Ответ «раскраска в три цвета существует» бесполезен, если раскраску не предъявили.

Для многих задач одно сводится к другому, и это стоит увидеть на примере выполнимости. Пусть у нас есть подпрограмма $\mathrm{ЕстьЛи}(\varphi)$, отвечающая «да/нет» за полиномиальное время. Тогда решение находится так: подставим $x_1=0$ и спросим, выполнима ли получившаяся формула. Если да — фиксируем $x_1=0$; если нет — фиксируем $x_1=1$ (ведь исходная формула выполнима, значит, хоть одно значение годится). Переходим к $x_2$. За $n$ обращений набор построен.

Такое свойство называют самосводимостью, и есть оно далеко не у всех задач. Поэтому формулировка Левина — не пересказ формулировки Кука, а самостоятельное утверждение: он строит универсальные задачи поиска, к которым сводится поиск в любой переборной задаче.

Оптимальный алгоритм существует

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

Теорема (универсальный поиск Левина). Пусть требуется по $y$ найти $x$ такой, что $f(x)=y$, причём проверка $f$ быстрая. Тогда существует алгоритм $U$, оптимальный с точностью до постоянного множителя: если какой-нибудь алгоритм $A$ решает эту задачу за время $t_A(y)$, то $U$ решает её за время не более $c_A\cdot t_A(y)+c_A$, где $c_A$ зависит только от $A$ и не зависит от $y$.

Построение занимает строчку. Занумеруем все программы: $p_1,p_2,p_3,\dots$ Запустим их все сразу, выделив программе номер $i$ долю $2^{-i}$ общего времени (доли в сумме дают единицу, так что времени хватит). Как только какая-то программа что-нибудь выдала, проверяем ответ функцией $f$; при успехе — останавливаемся.

Если лучший алгоритм имеет номер $i$, то он получит свою долю времени и справится, а мы потратим примерно в $2^{i}$ раз больше — то есть в постоянное число раз.

Смысл этого утверждения двойственный, и оба смысла настоящие.

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

Отрезвляющий. Константа равна двойке в степени длины программы. Для программы в тысячу знаков это $2^{1000}$. Пользоваться нельзя; знать полезно.

И заодно видно, чего $\mathrm{P}$ против $\mathrm{NP}$ на самом деле касается: не изобретательности, а того, существует ли вообще быстрый алгоритм — потому что если существует, универсальный поиск его найдёт.

Судьба

Леонид Левин родился в 1948 году в Днепропетровске. Учился в МГУ у Колмогорова, окончил в 1970-м, в 1972-м завершил кандидатскую работу.

Академической карьеры в СССР у него не вышло: он работал в Институте проблем передачи информации, потом в отраслевом институте автоматизации — то есть программистом. В 1978 году эмигрировал; в 1979-м получил степень в MIT, с 1980 года преподаёт в Бостонском университете.

Его результат добирался до западного читателя долго: перевод журнала выходил с задержкой, а по-настоящему западные специалисты поняли, что было сделано в Москве, после обзора Б. А. Трахтенброта «A survey of Russian approaches to perebor» (1984). С тех пор теорема называется двойным именем.

Что ещё он сделал

Ученик Колмогорова, Левин занимался главным образом колмогоровской сложностью — мерой количества информации в отдельном объекте, определяемой как длина кратчайшей программы, которая его печатает.

• Теорема кодирования Левина: универсальная априорная вероятность объекта с точностью до постоянного множителя равна $2^{-K}$, где $K$ — его колмогоровская сложность. Иначе говоря, вероятность того, что случайная программа напечатает данный объект, определяется тем, насколько коротко его можно описать. Это математическое выражение бритвы Оккама.
• Сложность $Kt$ — вариант, учитывающий не только длину программы, но и время её работы; именно из неё вырастает универсальный поиск.
• Сложность в среднем. В 1984 году Левин основал ещё одно направление: теорию сложности в среднем, где задача рассматривается вместе с распределением входов. Оказалось, что и там есть свои полные задачи. Практический смысл прямой: криптография нуждается в задачах, трудных не в худшем случае, а почти всегда.

Задача. Предположим, у вас есть быстрая подпрограмма, отвечающая «да/нет» на вопрос о выполнимости булевой формулы. Постройте по ней быстрый алгоритм, находящий сам набор значений переменных.
(Ответ: подставьте $x_1=0$ и спросите подпрограмму про упрощённую формулу. Если ответ «да» — оставьте $x_1=0$; иначе положите $x_1=1$ (раз исходная формула выполнима, а с нулём — нет). Повторите для $x_2,\dots,x_n$. Всего $n$ обращений; каждое дешёвое. Это и есть самосводимость выполнимости — свойство, из-за которого для неё «найти» и «узнать, есть ли» стоят одинаково.)

Следующая точка: Урбана — где перебор впервые доведут до конца машиной и получат теорему, которую ни один человек не проверит целиком.