Письмо Гёделя

Оракул из прошлой главы закрыл лавку: программы, которая про любую программу скажет, остановится ли та, не бывает. Но кончилась глава задачей по другую сторону границы — формулой из ста логических переменных. Как узнать, можно ли сделать её истинной, понятно: перебрать $2^{100}$ наборов значений. Только перебор займёт тысячи возрастов Вселенной. Разрешимо — ещё не значит решаемо. Вот задача того же рода, понятная ребёнку. Хозяйка рассаживает гостей за круглым столом и хочет, чтобы каждый сидел рядом только со знакомыми. Чтобы проверить готовую рассадку, достаточно обойти стол. Найти её — другое дело.

Тысячу гостей проверка обошла за десятые доли миллисекунды. Поиск для десяти занял десятые доли секунды, и каждый новый гость умножает время на число гостей: порядков за столом $(n-1)!$. Пятнадцать гостей — порядка полусуток, двадцать — пара тысяч лет, двадцать пять — миллиарды лет, сравнимо с возрастом Вселенной. Может, перебор — глупый способ, и умный алгоритм найдёт рассадку быстро? С сортировкой так и вышло: в главе 20 перебор всех порядков сменился $n \log n$. Для рассадки такого алгоритма за пятьдесят лет не нашёл никто, и никто не доказал, что его нет. Об этом вопросе вся глава; ещё в главе 13 мы обещали до него добраться.

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

Принстон, 20 марта 1956. Письмо Гёделя

Перескажем письмо на языке прошлой главы. Общая задача «доказуема ли формула» неразрешима: доказательство может быть любой длины, и поиск может длиться вечно. Гёдель ограничивает длину, и задача становится разрешимой тупым перебором: выписать все тексты не длиннее $n$ и каждый проверить. Проверка — механическая сверка строк с правилами. Беда в числе текстов: при алфавите из $k$ знаков их $k^n$.

Всё это можно увидеть в миниатюре. Дуглас Хофштадтер в книге «Гёдель, Эшер, Бах» (1979) придумал игрушечную формальную систему MIU. В ней одна аксиома — строка MI — и четыре правила вывода. Если строка кончается на I, к ней можно приписать U. Строку M$x$ можно заменить на M$xx$. Три I подряд можно заменить одной U. Две U подряд можно вычеркнуть. Теоремы системы — всё, что выводится из MI. Головоломка Хофштадтера: выводится ли MU?

Проверка вывода — один проход по строкам. Первый вывод верен, второй нет: из MIII правило 3 действительно даёт MU, но MIII из MII не получается. Поиск — обход в ширину из главы 19 по графу строк, и граф этот разрастается: за восемь шагов почти шестнадцать тысяч теорем, и волны растут всё быстрее: последняя почти вдесятеро больше предпоследней. MU среди них нет. Если бы вывод MU существовал, он когда-нибудь нашёлся бы, но сколько ни ищи, отсутствие находки ничего не доказывает.

MU и правда не выводится, только доказывают это совсем иначе. Число букв I в аксиоме равно одному и на три не делится. Правило 2 удваивает его, правило 3 уменьшает на три, правила 1 и 4 его не трогают. Ни одно из этих действий не сделает число, не кратное трём, кратным трём, поэтому нуля букв I не получится никогда, а в MU их ноль. Довод короткий, выводов не перебирает и проверяется за минуту. К вопросу «как доказать, что решения нет» мы вернёмся в конце главы.

Если бы поиск доказательства длины $n$ стоил порядка $n^2$ шагов, любая теорема с доказательством разумной длины, скажем в миллион символов, находилась бы машиной быстро. Математики остались бы нужны — задавать вопросы и понимать ответы, но искать доказательства им бы уже не пришлось. Через пятнадцать лет вопрос задали заново, независимо от Гёделя, и начали с задач поскромнее.

Проверить или найти

Прежде чем читать дальше, проведите опыт на себе. Ниже — судоку и секундомер. Сначала решите головоломку: секундомер запустится с первой цифрой. Потом откройте вкладку «Проверить»: там лежит решение, которое прислал друг, и в нём, может быть, есть ошибка. Найдите её или подтвердите, что ошибки нет. Сравните два времени.

У большинства людей решение занимает минуты, проверка — десятки секунд. Проверка идёт по готовому плану: 81 клетка, у каждой три группы — строка, столбец, квадрат. Это $3 \cdot 81 = 243$ взгляда, и никаких сомнений, что делать дальше. Поиск состоит из выборов, и за каждым выбором прячутся следующие. Вкладка «Машина» показывает то же в цифрах. Перебору с возвратом, который мы видели внутри регулярных выражений в главе 54, на доске 9×9 хватает сотен или тысяч попыток, а на 16×16 не хватает и десятков миллионов. Проверка растёт вместе с числом клеток: 243 взгляда, потом 768. Умный порядок — сначала клетка, где меньше всего вариантов, — спасает доску 16×16, но на 25×25 сдаётся и он. Хитрость отодвинула стену на одну доску дальше.

Газетная доска 9×9, конечно, решается компьютером за миллисекунды любым способом. Теория сложности говорит о семействе задач и о том, как растёт работа с размером. Судоку $n^2 \times n^2$ — бесконечное семейство досок, и для него вопрос «найти так же легко, как проверить?» имеет смысл. Ответ пока никому не известен.

Вопросы с ответом «да» или «нет»

Чтобы спор о «легко» и «трудно» стал точным, договоримся, о чём спорим. Теория имеет дело с задачами, у которых ответ — одно слово.

• Можно ли рассадить этих гостей так, чтобы соседи были знакомы?
• Можно ли дописать эту доску судоку до правильной?
• Есть ли у формулы доказательство не длиннее $n$ символов?
• Можно ли объехать эти города, проехав не больше 1000 км?

Такую задачу называют задачей распознавания: вход — текст, граф, доска, ответ — «да» или «нет». Неразрешимые задачи прошлой главы были того же рода. На деле, конечно, нужны сама рассадка и сам маршрут, но одно добывается из другого. Умея отвечать, есть ли маршрут не длиннее $L$, кратчайшую длину найдём двоичным поиском по $L$, как в двадцати вопросах из главы 20, а сам маршрут — выбрасывая дороги по одной и спрашивая, остался ли ответ «да». Быстрый ответ «да или нет» превращается в быстрый поиск.

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

Бюро стандартов, 1965. Хорошие алгоритмы

Говорят, что алгоритм работает за полиномиальное время, если на входе длины $n$ он делает не больше $C \cdot n^k$ шагов при каких-то постоянных $C$ и $k$. Линейное, $n \log n$, квадратичное, кубическое время из главы 13 — полиномиальные. Экспонента $2^n$ и факториал $n!$ — нет. А класс P — это все задачи распознавания, которые решаются за полиномиальное время. Кратчайший путь из главы 24, остовное дерево из главы 23, паросочетание, связность, сортировка — всё это P.

Границу провели здесь по трём причинам. Полиномы замкнуты: полиномиальное число вызовов полиномиального алгоритма — снова полином, $n^3$ вызовов по $n^2$ — это $n^5$, и из хороших деталей собирается хорошая машина. Класс не зависит от машины: машина Тьюринга, Python и процессор «Искры-8» подражают друг другу, как в главе 55, и замедление при этом полиномиальное, поэтому P для всех одно и то же. И наконец, у задач, для которых полиномиальный алгоритм нашёлся, степень почти всегда маленькая.

Есть и оговорка: алгоритм за $n^{100}$ формально хорош, а на деле бесполезен. Так что P значит скорее «без перебора», чем «быстро»: у задачи нашлась структура, и все варианты просматривать не нужно.

Май 1971. Доклад Кука

Доклад Кука держится на трёх понятиях, и первое из них — подсказка.

Подсказка в конверте

Вернитесь к рассадке гостей. Найти её трудно, но если кто-то пришлёт рассадку в конверте, мы проверим её за один обход стола. У судоку подсказка — заполненная доска, у формальной системы — вывод, у составного числа — делитель. Во всех случаях ответ «да» можно подтвердить коротким документом, который быстро проверяется. Такой документ называют сертификатом, а программу, которая его проверяет, — проверяющей. В главе 26 мы уже встречали сертификат под другим именем: свидетель Миллера — Рабина доказывает, что число составное.

Класс NP — это задачи распознавания, у которых для каждого ответа «да» есть сертификат полиномиальной длины, проверяемый за полиномиальное время, а для ответа «нет» никакой сертификат проверку не пройдёт. Рассадка, судоку $n^2 \times n^2$, вопрос Гёделя о доказательстве длины не больше $n$ — всё это NP. Буквы расшифровываются как «недетерминированное полиномиальное время». Вспомните автомат, который угадывает, из главы 54: он идёт сразу всеми путями и принимает строку, если хоть один путь ведёт к успеху. Машина Тьюринга, которая так же угадывает сертификат и потом его проверяет, решает любую задачу из NP за полиномиальное число шагов. Только машины из железа угадывать не умеют, и им остаётся перебирать подсказки подряд.

Одна функция search решает все три задачи: ей нужна только проверяющая программа. Делитель 17 нашёлся на восемнадцатой попытке, судоку — на 1610-й из $4^6 = 4096$, рассадка — на 25 528-й из $7^7 = 823\,543$. Этим способом любая задача из NP решается за экспоненциальное время: подсказок длины $p(n)$ из $k$ букв всего $k^{p(n)}$. И P лежит внутри NP: если задачу можно решить быстро, проверяющая программа найдёт ответ сама, без подсказки. Знаменитое $\mathrm{P} \stackrel{?}{=} \mathrm{NP}$ спрашивает об обратном: можно ли для каждой задачи, где ответ легко проверить, научиться так же легко его находить?

Сведение

Второе понятие — полиномиальное сведение. Сведения из прошлой главы переделывали один вопрос о программах в другой, чтобы перенести неразрешимость. Здесь то же, но с оглядкой на время. Задача A сводится к задаче B, если любой вход A можно за полиномиальное время переделать во вход B так, что ответы совпадут. Тогда B не легче A: быстрый алгоритм для B вместе со сведением даёт быстрый алгоритм для A.

В следующей главе пригодится такое сведение. Рассадка гостей сводится к задаче коммивояжёра: можно ли объехать все города, проехав не больше $L$? Гости становятся городами. Между знакомыми — дорога длины 1, между незнакомыми — длины 2. Рассадка существует тогда и только тогда, когда есть объезд $n$ городов длиной не больше $n$: такой объезд ходит только по дорогам длины 1, то есть только между знакомыми. Переделка занимает $n^2$ шагов — по одной дороге на пару. Значит, коммивояжёр не легче рассадки. Если завтра кто-то найдёт быстрый алгоритм для коммивояжёра, хозяйки всего мира скажут ему спасибо.

Выполнимость

Третье понятие — задача, к которой Кук свёл всё остальное. Возьмём переменные $x_1, x_2, \ldots$, каждая может быть истиной или ложью. Литерал — это переменная или её отрицание: $x_3$ или $\neg x_3$. Условие — «или» нескольких литералов: $(x_1 \lor \neg x_2 \lor x_4)$. Формула в конъюнктивной нормальной форме, КНФ, — это «и» нескольких условий. Это зеркало дизъюнктивной формы из главы 29: там «или» произведений, здесь «и» сумм.

Задача выполнимости, SAT от английского satisfiability, спрашивает: можно ли так выбрать значения переменных, чтобы в каждом условии был хотя бы один истинный литерал. У формулы выше ответ «да»: $x_1$ — истина, $x_2$ — истина, $x_3$ — ложь. Сертификат — набор значений, проверка — один проход по условиям, так что SAT лежит в NP. Перебор — $2^n$ наборов. В программах формулу записывают так, как это принято на соревнованиях SAT-решателей: переменная — номер, отрицание — минус, условие — список: [[1, -2], [2, 3, -1], [-3, -1]]. Если в каждом условии не больше трёх литералов, задачу называют 3-SAT.

Задачу из NP, к которой сводится любая задача из NP, называют NP-полной. Теорема говорит, что SAT NP-полна: это самая трудная задача NP, и вся трудность класса сосредоточена в ней одной.

Машина в формуле

Полное доказательство занимает несколько страниц, но идея помещается в абзац, и её можно собрать из деталей этого курса. Пусть задача лежит в NP. Значит, есть проверяющая программа, которая за $p(n)$ шагов читает вход и сертификат и говорит «да» или «нет». Программа работает на процессоре, а процессор, как мы собрали его в главах 29–32, — это вентили и регистры, которые обновляются на каждом такте. Развернём время: нарисуем схему процессора $p(n)$ раз подряд, выходы регистров такта $t$ подадим на входы такта $t + 1$. Получится одна огромная схема без памяти и без часов — но полиномиального размера. Её входы — биты задачи, которые мы знаем, и биты сертификата, которых не знаем. Выход — ответ проверки. Вопрос «есть ли сертификат» превратился в вопрос «можно ли подать на свободные входы такие биты, чтобы на выходе загорелась единица».

Осталось перевести схему в формулу. Каждому проводу — переменная, каждому вентилю — несколько условий: они выполнены, когда вентиль работает правильно, и нарушены, когда нет. Для вентиля «и» с входами $a, b$ и выходом $c$ это три условия: $(\neg c \lor a)$, $(\neg c \lor b)$, $(c \lor \neg a \lor \neg b)$. Этот перевод схем в формулы придумал ленинградский логик Григорий Цейтин в середине 1960-х, и его так и называют — преобразованием Цейтина. Проверим условия перебором всех восьми случаев.

Условия выполнены в четырёх строках из восьми — как раз там, где out равен «a и b». Так же переводятся «или», «не», исключающее «или», а значит, и сумматор, и вся схема. К условиям вентилей добавляем однобуквенные условия: известные входы равны битам задачи, выход равен единице. Формула выполнима тогда и только тогда, когда сертификат существует, а её размер — число вентилей, умноженное на константу.

Ту же идею можно повернуть другой стороной и сделать из неё инструмент. Возьмём схему умножителя — сдвиги и сумматоры из главы 30 — и потребуем, чтобы на выходе стояло заданное число $n$, а множители были больше единицы. Решатель формул, найдя выполняющий набор, прочтёт на входах множители: он прогонит умножитель задом наперёд. В модуле cs.sat песочницы лежит класс Circuit, который строит такие схемы вентиль за вентилем, и решатель solve. Как устроен решатель, вы узнаете, когда напишете свой в задаче «Свой SAT-решатель».

Решатель ничего не знает о числах. Он видит тысячи условий вида «этот провод — исключающее или тех двух», ищет набор, при котором все они выполнены, — и находит множители. Раскладывать числа так невыгодно: на таких размерах перебор делителей быстрее. Дело в самой возможности. Разложение на множители — задача из NP, сертификат в ней — делитель. Значит, она сводится к SAT, и быстрый решатель SAT разложил бы на множители и 2048-битное число, на котором держится шифр RSA (о нём — в главе 60). Пока же тупиков с ростом числа всё больше: у трёхзначного один, у десятизначного — тысячи. До 1024 бит в каждом множителе этот решатель не доберётся никогда.

Москва, 1973. Две страницы Левина

Кук спрашивал «да или нет?», Левин — «найди». У второй постановки есть следствие, в которое с первого раза трудно поверить.

Беркли, 1972. Двадцать одна задача

Чтобы доказать, что новая задача NP-полна, не нужно повторять доказательство Кука. Достаточно двух вещей: показать, что задача лежит в NP, и свести к ней какую-нибудь задачу, про которую уже известно, что она NP-полна. Сведения складываются в цепочки: если SAT сводится к A, а A — к B, то SAT сводится и к B. Так от одной выполнимости выросло дерево Карпа.

Здесь много знакомых: рюкзак из главы 22, дерево Штейнера, о котором предупреждала глава 23, рассадка гостей под именем гамильтонова цикла, покрытие множествами, которое вернётся в следующей главе. Каждое сведение — маленькое изобретение: одну задачу надо собрать из деталей другой. Такие детали называют гаджетами. Посмотрим поближе на самое наглядное из сведений Карпа — от 3-SAT к клике.

Клика в графе — это группа вершин, где каждые две соединены ребром: компания, в которой все знакомы друг с другом. Задача о клике спрашивает, есть ли в графе клика из $k$ вершин. Сертификат — сама клика, проверка — $k^2$ взглядов. Сведение строится так. Каждое условие формулы даёт три вершины, по одной на литерал. Рёбра проводим между литералами разных условий, кроме противоречащих: $x_2$ и $\neg x_2$ не соединяем. Число $k$ — число условий.

Ответы у двух задач совпадают. Если формула выполнима, возьмём в каждом условии по истинному литералу: это $k$ вершин из разных троек, и никакие две не противоречат друг другу, ведь истинны обе. Все пары соединены — клика. Обратно, внутри тройки рёбер нет, поэтому клика из $k$ вершин берёт по одной вершине из каждого условия, и противоречащих среди них нет. Объявим эти литералы истинными — каждое условие выполнено. Граф строится за время порядка квадрата длины формулы. Значит, клика NP-полна: быстрый поиск клик дал бы быстрый SAT, а с ним — всё NP.

Следите за направлением сведения. Чтобы доказать, что клика трудна, мы переделали в клику известную трудную задачу, а не наоборот. Перепутать направление — самая частая ошибка: если свести свою задачу к SAT, это докажет лишь, что она не труднее SAT. Зато такое сведение — лучший практический способ её решить. Современные SAT-решатели справляются с формулами из миллионов переменных, и многие трудные задачи выгоднее перевести в формулу и отдать решателю, чем решать самому. В задаче «Раскраска в формулу» вы так переведёте раскраску карты, а в следующей главе решатель будет разгадывать судоку.

О судоку. Японские исследователи Такаюки Ято и Такахиро Сэта в 2003 году доказали, что задача «можно ли дописать доску $n^2 \times n^2$» NP-полна. Так что полиномиальный алгоритм для судоку любого размера ответил бы на вопрос Гёделя и принёс бы автору миллион долларов, о котором ниже.

Стэнфорд, 1974. Бюллетень Кнута

Задачу называют NP-трудной, если к ней сводится любая задача из NP. NP-полные — это NP-трудные, которые сами лежат в NP. Отдельное слово понадобилось потому, что многие нужные на практике задачи не имеют вида «да или нет». Найти кратчайший объезд городов — это заказ на маршрут, и никто не знает сертификата, который быстро подтвердил бы, что короче не бывает. Такая задача NP-трудна: умея её решать, мы ответим и на вопрос «есть ли объезд не длиннее $L$».

Бывают NP-трудные задачи и пострашнее. Проблема остановки из прошлой главы NP-трудна. Сведём к ней выполнимость: по формуле напишем программу, которая перебирает все наборы и останавливается, найдя выполняющий, а если не найдёт — уходит в вечный цикл. Программа остановится тогда и только тогда, когда формула выполнима, а написать её можно за полиномиальное время. В NP проблема остановки при этом не лежит: она даже не разрешима. Так что «NP-трудна» говорит только о нижней границе трудности; сверху задача может быть сколь угодно тяжёлой.

Пора вернуть долг главе 22. Рюкзак стоит в дереве Карпа, значит, он NP-полон. Но мы решали его таблицей за $n \cdot W$ шагов, где $W$ — вместимость. Разве это не полиномиальное время? Вспомните уговор о размере входа: число $W$ записано $\log_{10} W$ цифрами. Добавьте к весам одну цифру точности — граммы вместо десятков граммов, — и вход станет длиннее на $n$ символов, а таблица — в десять раз шире.

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

Париж, 2000. Если P = NP

24 мая 2000 года в Париже Математический институт Клэя объявил семь «задач тысячелетия» с премией в миллион долларов за каждую. P против NP — среди них (о шести других — в «Царице наук»). Официальное описание задачи для института писал Кук, и в нём есть фраза, от которой становится неуютно: алгоритм, решающий 3-SAT за $n^2$ шагов, раскладывал бы на множители 200-значные числа за несколько минут. Почему, мы уже видели: умножитель, запущенный задом наперёд, — всего лишь формула.

Представим, что кто-то доказал $\mathrm P = \mathrm{NP}$, и алгоритм к тому же практичен, со степенью 2 или 3. Тогда исчезла бы почти вся криптография: ключ шифра, который можно проверить, нашёлся бы через формулу. Зато расписания, маршруты, раскрой, размещение элементов на кристалле стали бы решаться точно. Сбылась бы мечта Гёделя: доказательство любой теоремы, если оно разумной длины, искала бы машина. Слишком уж хорош был бы такой мир, и почти никто в него не верит.

Даже если $\mathrm P \ne \mathrm{NP}$, криптографии этого мало. Неравенство говорит, что NP-полные задачи трудны в худшем случае, а шифру нужно, чтобы трудным был почти каждый ключ. К тому же разложение на множители, на котором держится RSA, NP-полным не считают: у него есть сертификаты и для «да», и для «нет». Ричард Ладнер в 1975 году доказал, что если $\mathrm P \ne \mathrm{NP}$, между P и NP-полными задачами обязательно есть промежуточные, и разложение — главный кандидат в них. Поэтому надёжность шифров держится не на теоремах, а на опыте: их десятилетиями пытались сломать и не смогли. Об этом — часть X.

Карта местности

Всю переписку можно свести на одну карту. Кроме P и NP, на ней есть ещё несколько стран.

co-NP — зеркало NP: задачи, где коротким сертификатом подтверждается ответ «нет». Формула невыполнима? Гостей нельзя рассадить? Иногда находится короткий довод, как инвариант для MU, но в общем случае никто не знает сертификата лучше, чем «я перебрал всё». Армин Хакен в 1985 году доказал, что для формулы «$n + 1$ голубь не помещается в $n$ клеток по одному» любое доказательство невыполнимости методом резолюций, которым пользуются SAT-решатели, экспоненциально длинное. Верят, что $\mathrm{NP} \ne \text{co-NP}$, но и это не доказано.

PSPACE — задачи, которые решаются с полиномиальной памятью, сколько бы шагов это ни заняло. Сюда входит всё NP: подсказки можно перебирать по одной на одном и том же месте. Типичные жители PSPACE — игры: «есть ли у белых ход, такой что на любой ответ чёрных есть ход, такой что…» — и выигрышная стратегия в короткий сертификат не помещается. Дальше — EXPTIME. Шахматы на доске $n \times n$, как доказали Авиезри Френкель и Дэвид Лихтенштейн в 1981 году, полны в EXPTIME, и быстрого алгоритма для них заведомо нет. А за всеми классами — неразрешимые задачи прошлой главы.

Про цепочку $\mathrm P \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}$ известно, что она не может состоять из одних равенств: по теореме Хартманиса и Стернса $\mathrm P \ne \mathrm{EXPTIME}$. Значит, хотя бы одно из трёх включений строгое. Какое — не знает никто. Может быть, все три.

В работе из всего этого пригодится умение узнавать трудную задачу в лицо. Если требуется выбрать подмножество, порядок или раскраску, ответ легко проверить, а все попытки упираются в перебор, поищите задачу среди NP-полных: в справочнике Гэри и Джонсона 1979 года их больше трёхсот, сегодня известны тысячи. Если нашлась, не тратьте неделю на поиск точного быстрого алгоритма, которого не нашли тысячи людей до вас. Тратьте её на то, что работает, — об этом следующая глава.

Задачи

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

Куда дальше

Переписка не закончена. Вопрос Гёделя открыт, премия Клэя не выплачена, и большинство специалистов уверены, что $\mathrm P \ne \mathrm{NP}$: для рассадки, судоку, выполнимости и тысяч их родственников быстрого точного алгоритма нет. Задача, которую вы встретите на работе, легко может оказаться одной из них. Распределить заказы по курьерам, составить расписание смен, разместить склады, разрезать листы фанеры с наименьшими обрезками — все они NP-трудны.

Между тем службы доставки каждое утро строят маршруты для тысяч машин. Заводы режут фанеру. Компиляторы раскрашивают графы регистров, а решатель из этой главы разложил на множители десятизначное число примерно за секунду. В 2006 году объезд 85 900 точек был найден и доказан кратчайшим. Противоречия тут нет: NP-трудность говорит о худшем случае и о точности до последнего метра. Стоит согласиться на маршрут, который хуже лучшего на один процент, или взять задачи из жизни, а не построенные злым шутником, и картина меняется. Как логисты каждый день справляются с NP-трудными задачами, покажет следующая глава: там вы сами проложите маршрут через тридцать три города и посоревнуетесь с алгоритмами.