Класс P: что значит «решается быстро»

Если ты определишь класс P, объяснишь, почему граница проведена по многочлену, и скажешь, почему перебор делителей не полиномиальный алгоритм, - листай до «Теперь сам».

Как думаешь, быстрый ли это алгоритм

Проверка числа на простоту: перебрать делители от двух до корня из числа. Для числа около миллиона это тысяча делений, для числа около триллиона - миллион. Корень из n растёт медленнее самого n; звучит как очень хороший алгоритм.

Ответь себе до чтения: за сколько он проверит число, которое записывается сотней десятичных цифр? Корень из такого числа - это пятьдесят цифр, 10⁵⁰ делений. Не хватит времени жизни Вселенной. При этом вход занимает одну строку текста. Алгоритм, который выглядел сублинейным, экспоненциален, если мерить его тем, чем мерят все алгоритмы, - длиной входа.

На что это похоже

Два способа найти слово в бумажном словаре. Открывать посередине и отбрасывать половину - число действий растёт на одно при удвоении словаря. Проверять все возможные сочетания букв, пока не получится слово, - число действий умножается на тридцать три с каждой новой буквой.

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

Механизм: время как функция длины входа

Задача разрешения - задача с ответом «да» или «нет»; формально это язык: множество входов с ответом «да». Задачу на оптимум превращают в задачу разрешения порогом: не «найди кратчайший путь», а «есть ли путь не длиннее k».

Длина входа n - число символов в его записи: бит, если быть точным. Граф записывается числом вершин и списком рёбер, число - своими цифрами. Число N занимает около log₂ N бит.

Время работы алгоритма - наибольшее число шагов на входах длины n, как функция от n. Алгоритм полиномиален, если это время ограничено сверху c · nᵏ для каких-то постоянных c и k.

Класс P - все задачи разрешения, для которых существует полиномиальный алгоритм.

Почему граница проведена именно здесь.

устойчивость к модели   одна лента, много лент, память с адресами -
                        разница в пределах многочлена (глава о машине
                        Тьюринга), так что «полиномиально» значит
                        одно и то же везде
устойчивость к сборке   многочлен от многочлена - многочлен:
                        полиномиальная программа, которая полиномиальное
                        число раз вызывает полиномиальную, остаётся
                        полиномиальной
разрыв с экспонентой    nᵏ при удвоении входа растёт в 2ᵏ раз -
                        в постоянное число;
                        2ⁿ при удвоении входа возводится в квадрат

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

Что лежит в P: почти весь этот курс, если задачи переписать как вопросы с ответом «да» или «нет»: для оптимизации это вопрос с порогом, для сортировки - например, «стоит ли на k-м месте после сортировки число не больше x». Сортировка, кратчайшие пути, остовные деревья, потоки и паросочетания, выполнимость формул с двумя литералами в скобке, разбор КС-грамматик, линейное программирование, проверка простоты числа - последнее доказано только в 2002 году.

Есть ли разрешимые задачи вне P? Да, и это доказано: с экспоненциальным запасом времени решается строго больше задач, чем с полиномиальным. Пример - «выигрывает ли первый игрок из данной позиции» в шахматах, обобщённых на доску n × n: доказано, что полиномиального алгоритма для неё нет.

Правило

Класс P - задачи разрешения, решаемые алгоритмом за время не больше c · nᵏ, где n - длина записи входа в битах. Многочлен выбран за устойчивость: класс не зависит от выбора разумной модели вычислений и замкнут относительно вызова одной программы из другой. Время, выраженное через величину числа на входе, а не через длину его записи, полиномиальным не считается.

Разбор: сколько это в годах

Пусть машина делает миллиард операций в секунду; для простоты счёта примем миллиард за 2³⁰. Функция vremya переводит секунды в привычные единицы. Сравним n², n⁵ и 2ⁿ. Машина делает 2³⁰ операций в секунду, поэтому 2ⁿ операций - это 2ⁿ⁻³⁰ секунд; для n = 1000 число не помещается в тренажёр, и в клетке стоит не замер, а слова.

def vremya(sekund):
    if sekund < 1:
        return "меньше секунды"
    if sekund < 3600:
        return str(sekund) + " с"
    if sekund < 86400 * 365:
        return str(sekund // 3600) + " ч"
    return str(sekund // (86400 * 365)) + " г"

for n in [20, 40, 60, 80, 1000]:
    kvadrat = vremya(n ** 2 // 2 ** 30)
    pyataya = vremya(n ** 5 // 2 ** 30)
    if n <= 80:
        eksponenta = vremya(2 ** (n - 30))
    else:
        eksponenta = "не дождаться"
    print(n, "|", kvadrat, "|", pyataya, "|", eksponenta)

20 | меньше секунды | меньше секунды | меньше секунды
40 | меньше секунды | меньше секунды | 1024 с
60 | меньше секунды | меньше секунды | 34 г
80 | меньше секунды | 3 с | 35702051 г
1000 | меньше секунды | 258 ч | не дождаться

Столбцы: n, время для n², для n⁵ и для 2ⁿ. Экспонента при n = 40 - семнадцать минут, при n = 60 - тридцать четыре года, при n = 80 - тридцать пять миллионов лет. Каждые двадцать единиц длины умножают время в миллион раз. Машина в тысячу раз быстрее отодвинула бы каждую строку на десять единиц n - и только.

Последняя строка - предостережение в другую сторону. n⁵ при n = 1000 - это 258 часов, почти одиннадцать суток. Полиномиальность не означает скорость; она означает, что удвоение входа обойдётся в постоянный множитель, здесь в тридцать два раза, а не в возведение времени в квадрат.

Разбор: перебор делителей и длина записи

Функция delitel ищет наименьший делитель числа, перебирая кандидатов до корня, и считает проверки. Первые пять чисел простые - для них перебор проходит до конца. В первом столбце вывода - длина числа в битах.

def delitel(n):
    proverok = 0
    d = 2
    while d * d <= n:
        proverok = proverok + 1
        if n % d == 0:
            return [d, proverok]
        d = d + 1
    return [n, proverok]

for chislo in [251, 65521, 1048573, 16777213, 268435399]:
    bit = 0
    m = chislo
    while m > 0:
        bit = bit + 1
        m = m // 2
    print(bit, chislo, delitel(chislo))
print(delitel(268435399 - 2), delitel(1000001))

8 251 [251, 14]
16 65521 [65521, 254]
20 1048573 [1048573, 1022]
24 16777213 [16777213, 4094]
28 268435399 [268435399, 16382]
[29, 28] [101, 100]

Числа в списке - наибольшие простые не длиннее 8, 16, 20, 24 и 28 бит. Четыре лишних бита в записи числа - вчетверо больше проверок: 1022, 4094, 16 382. Число проверок - около 2 в степени половины длины записи. Для числа из 256 бит это 2¹²⁸ делений. Формула «корень из n» правдива, но n в ней - величина числа, а не длина входа. Через длину входа b она читается как 2 в степени b/2, и это экспонента.

Последняя строка вывода - составные числа: делитель нашёлся за 28 и за 100 проверок. Перебор бывает быстрым, когда повезло с входом; время работы алгоритма определяется худшим случаем, а худший случай здесь - простое число.

Полиномиальная проверка простоты существует, и устроена она совсем иначе: не ищет делитель, а проверяет свойства остатков. Вероятностная проверка встречалась в главе про RSA; детерминированный полиномиальный алгоритм найден в 2002 году. А вот найти сам делитель составного числа за полиномиальное время на обычном компьютере не умеет никто, и шифр RSA на это опирается: разложив модуль, его вскрывают сразу.

Что ломается без этого

Время считают от величины числа. «Цикл до n» при n на входе - экспонента от длины записи. Так ошибаются с простотой, с рюкзаком (таблица «предметы на вместимость» растёт с величиной вместимости, а не с длиной её записи), с любой задачей, где на входе большие числа.

«Полиномиальный - значит быстрый». n⁵ на тысяче элементов - одиннадцать суток. P - граница принципиальной осуществимости, а не обещание скорости.

«Экспоненциальный - значит бесполезный». При n = 20 экспонента - меньше секунды. Точный перебор на маленьких входах - законный инструмент; раздел о сложных задачах к нему вернётся.

«Ускорим железом». Тысячекратное ускорение даёт экспоненциальному алгоритму десять лишних единиц длины входа. Полиномиальному n² оно даёт вход в тридцать раз больше.

Зачем это в работе

Первый вопрос к новой задаче. До выбора алгоритма полезно понять, по какую сторону границы задача: если она в P, полиномиальный алгоритм существует и его можно искать; если есть основания думать, что нет, - искать нужно не его, а приемлемый компромисс.

Оценка масштаба. Когда вход - список записей ограниченной длины, n можно считать числом записей: длина входа отличается от него в постоянное число раз. Алгоритм n² на миллионе записей - это 10¹² операций, минут пятнадцать; n³ - тридцать лет. Перевод степени в время - одна строка расчёта, которую стоит делать до написания кода.

Чтение условий. Ограничения в задаче подсказывают ожидаемую сложность: n до двадцати - можно перебирать подмножества; n до тысячи - квадрат; n до миллиона - нужно n log n или линия.

Теперь сам

1. Алгоритм делает n³ шагов. Во сколько раз вырастет время при удвоении входа?
2. Алгоритм делает 2ⁿ шагов и справляется с n = 40 за семнадцать минут. Сколько времени ему нужно при n = 50?
3. Программа получает число N и выполняет цикл из N итераций. Полиномиальна ли она?
4. Полиномиальная программа вызывает другую полиномиальную программу n² раз. Останется ли время полиномиальным?
5. Как превратить задачу «найти наибольшее паросочетание» в задачу разрешения?