Изменчивая природа математического доказательства. Доказать нельзя поверить

шагов, чтобы сложить всю колоду по порядку. Формулу сумы, которой мы воспользовались, обычно приписывают Гауссу; поскольку выполняется оценка , мы заключаем, что у этой задачи полиномиальная сложность степени 2 (по крайней мере не больше), где 2 — степень мажорирующего одночлена. А теперь сравним этот первый пример со знаменитой задачей о коммивояжере: заданы n городов, причем каждые два из них соединены дорогой (рис. 11.15), а каждой дороге приписана цена. Задача в том, чтобы найти маршрут, который проходит через все города, в конце приводит в исходную точку и имеет наименьшую стоимость.

Рис. 11.15. Задача о коммивояжере

Рис. 11.16. Задача о подграфе

На уровне эффективной вычислимости мы видим, что поиск решения задачи о коммивояжере сводится к проверке всех возможных порядков городов (ведь ясно, что коммивояжер может посещать города в любом порядке). Этих порядков всего

Мы можем оценить это число по формуле Стирлинга:

Ясно, что задачу нельзя решить (очевидным способом) за полиномиальное число шагов. Поэтому мы говорим, что это задача (потенциально) экспоненциальной сложности. На самом деле для строгого доказательства этого утверждения требуется еще несколько аргументов.

Еще одна знаменитая задача экспоненциальной сложности — задача о подграфе. Пусть G — граф. Иначе говоря, G — набор вершин и ребер, которые соединяют некоторые пары вершин. Пусть H — другой граф. Вопрос в том, содержит ли G подграф, изоморфный H (рис. 11.16). (Два графа называют изоморфными, если существует взаимно однозначное отображение их вершин и соответствующих ребер.)

11.7.2 Сравнение полиномиальной и экспоненциальной сложности

С точки зрения теоретических компьютерных наук довольно интересно знать, какова сложность задачи — полиномиальная или экспоненциальная, ведь именно эта информация указывает на то, насколько затратным будет решение с точки зрения вычислений. В области компьютерных игр (к примеру) она позволяет сказать: будет ли некоторое действие выполняться с реалистичной скоростью или растянется во времени.

В дальнейшем мы ограничим наше внимание на так называемых «задачах принятия решения». Ответом в таких задачах может быть только «да» или «нет». Примером задачи, которая не относится к этому классу, может служить задача оптимизации (вроде того, чтобы найти конфигурацию, которая что-то там максимизирует). Но даже большинство задач оптимизации можно превратить в задачи принятия решений, введя дополнительный параметр, играющий роль верхней границы. Ограничивать себя только задачами принятия решений — не такое уж суровое требование, однако оно сделает изложение прозрачным.

11.7.3 Полиномиальная сложность

Говорят, что задача относится к классу P, если существуют многочлен p и (детерминистская) машина Тьюринга (ДТМ), для которых любой набор вводимых данных объема n приводит к остановке с ответом «да» или «нет» не более чем за p шагов (машины Тьюринга мы обсуждали в разд. 7.1). Слово «детерминистская» используется для того, чтобы указать на эффективно вычислимый процесс, в котором не прибегают к угадыванию (в эти идеи мы углубимся ниже в разд. 11.7.5).

Считается, что задачи класса P легко решаемы. Задачи, которые к нему не относятся, для которых нет полиномиального алгоритма решения, по определению решить сложно. Решение задачи класса P требует разумного времени и существует всегда. Быть того не может, чтобы машина работала над решением вечно. Упорядочить карты в колоде (мы уже обсуждали эту задачу), найти определенный шарик в урне, разбить на пары гостей на вечеринке — все это задачи класса P. 

11.7.4 Утверждения, которые можно проверить за полиномиальное время

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

Скажем, задачу разложить данное n-значное натуральное число N на простые множители принято считать экспоненциально сложной (см. [SCL]). Правда, этот факт достоверно не установлен. Более точно, сложность (согласно наилучшему известному на сегодняшний день алгоритму) составляет примерно — столько шагов в этом алгоритме. Однако процедура проверки сложна всего лишь полиномиально: если для числа N предложено разложение p₁,...p_k, то всего лишь за полиномиальное время можно вычислить (следуя правилам арифметики) произведение p₁•p₂...p_k и убедиться, что оно равно (или не равно, — как повезет) числу N.