Полиномиальные и не полиномиальные задачи

Предположим, что /(и) и g{ri) — математические выражения. Утверждение, что g(n) ограничена f(ji), означает, что, вычисляя эти выражения на растущих значениях и, значения/(и) в итоге становятся больше значений g(n) и превышают g(n) на всех дальнейших значениях п. Другими словами, то, что g(n) ограничена/(и), означает, что график/(и) находится выше графика g(n) для «больших» значений п. Например, выражение lg п ограничено п (рис. 11.6, а), а п lg n ограничено п2 (рис. 11.6, б).

Мы называем задачу полиномиальной (polynomial problem), если она принадлежит О(/(и)), где f{n) — это полином (многочлен), или это выражение ограничено полиномом. Набор всех полиномиальных задач обозначается Р. Обратите внимание, что наши предыдущие исследования показали, что задачи поиска в списке и сортировки списка принадлежат Р. Утверждение о том, что задача является полиномиальной, говорит о времени, необходимом для решения задачи. Мы часто говорим, что задача из Р может быть решена в полиномиальное время или что у этой задачи решение с полиномиальным временем.

Поиск задач, принадлежащих Р, является одной из главных проблем вычислительной техники, так как он тесно связан с вопросами о том, существует ли для задач практическое решение. Действительно, задачи, не входящие в Р, характеризуются очень большим временем выполнения, даже для небольших входов. Например, представим себе задачу, решение которой выполняется за 2" шагов. Экспоненциальное выражение 2" не ограничено ни одним полиномом. Действительно, если f{n) — полином, то с увеличением значения п мы обнаружим, что значения 2" всегда будут больше значений /(я). Это означает, что алгоритм сложности Э(2") в общем случае будет менее эффективным, и для его выполнения потребуется больше времени, чем для алгоритма сложности Э(/(и)). Говорят, что для алгоритма, сложность которого определяется экспоненциальным выражением, требуется экспоненциальное время.

Рассмотрим пример. Представьте проблему перечисления всех возможных подгрупп, которые можно сформировать из группы, состоящей из п человек. Так как таких подгрупп может быть 2" — 1 (мы считаем подгруппой всю группу, но не допускаем пустых подгрупп), любой алгоритм для решения этой задачи должен состоять минимум из 2" - 1 шагов, и его сложность будет, по крайней мере, равна этому значению. Но выражение 2" - 1, будучи экспоненциальным, не ограничено ни одним полиномом. Следовательно, любое решение этой задачи по мере увеличения размера группы, из которой выбираются подгруппы, требует огромного времени выполнения.

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

То, что теоретически разрешаемые проблемы, не принадлежащие Р, имеют огромную временную сложность, заставляет нас признать, что их невозможно решить с практической точки зрения. Ученые, занимающиеся вычислительной техникой, называют такие задачи трудно разрешимыми. В свою очередь, задачи, для которых существуют практические решения, содержатся в Р. Поэтому понимание границ класса Р стало важной областью исследований вычислительной техники.

NP-задачи

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

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

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

Взять один из возможных путей и подсчитать общую длину пути. if (длина пути не превышает допустимой)

then (объявить об успехе)

else (ничего не объявлять)

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

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

Конечно, наше недетерминированное решение не идеально. Оно основано на случайном выборе. Однако его существования достаточно для предположения, что, возможно, есть и детерминированное решение задачи коммивояжера, которое выполняется в полиномиальное время. Правда это или нет — пока что открытый вопрос. В действительности, задача коммивояжера — лишь одна из задач, для которых известны недетерминированные решения, выполняемые в полиномиальное время, и для которых детерминированного решения с полиномиальным временем пока что не найдено. Дразнящая эффективность недетерминированных решений этих задач заставляет надеяться, что однажды будут найдены и эффективные детерминированные решения, но большинство убеждены, что эти проблемы все же слишком сложны и выходят за рамки возможностей эффективных детерминированных алгоритмов.