рата и Шамос [160], а также Эдельсбруннер [60].

Хотя сама геометрия имеет тысячелетнюю историю, алгоритмические задачи в геометрии стали рассматривать лишь недавно. Как отмечают Препарата и Шамос, впервые сложностью геометрических задач заинтересовался Лемуан (Е. Lemoine) в 1902 году. Изучая построения при помощи циркуля и линейки, он выделил пять элементарных действий (установить одну из ножек циркуля в данную точку, установить одну из ножек циркуля на данной прямой, нарисовать круг, приложить край линейки так, чтобы он проходил через данную точку, провести прямую). Лемуан интересовался минимальным числом действий, требуемых для решения данной задачи на построение.

Алгоритм раздела 35.2, выясняющий, есть ли в множестве отрезков пересекающиеся, разработали Шамос и Хой [176].

Грэхем (Grahm) описывает «просмотр Грэхема» в [91]. Алгоритм с «заворачиванием» принадлежит Джарвису [112]. Используя так называемые разрешающие деревья в качестве вычислительной модели, Яо доказал [205] нижнюю оценку fi(ralnra) на время работы любого алгоритма, находящего выпуклую оболочку.

Если интересоваться временем работы как функцией от числа всех точек (га) и от числа точек выпуклой оболочки (h), наиболее быстрым является метод «стрижки и поиска» (prune-and-search method), который придумали Киркпатрик и Зайдель [120]; требующий времени О (nigh). Этот алгоритм является асимптотически оптимальным.

Описанный нами алгоритм поиска пары ближайших точек (время работы O(ralnra)) предложил Шамос (см. Препарата и Шамос [160]). Препарата и Шамос показали, что этот алгоритм асимптотически оптимален в модели разрешающих деревьев.

NP-полнота

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

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

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

В этой главе мы рассмотрим класс задач, называемых «NP-полными». Для этих задач не найдены полиномиальные алгоритмы, однако не доказано, что таких алгоритмов не существует. Изучение NP-полных задач связано с так называемым вопросом Р ф NP. Этот вопрос был поставлен в 1971 году и является сейчас одной из наиболее интересных и сложных проблем теории вычислений.

Большинство специалистов полагают, что NP-полные задачи нельзя решить за полиномиальное время. Дело в том, что если хотя бы для одной NP-полной задачи существует решающий ее полиномиальный алгоритм, то и для всех NP-полных задач такие алгоритмы существуют. В настоящее время известно очень много NP-полных задач. Все попытки найти для них полиномиальные алгоритмы оказались безуспешными. По-видимому, таких алгоритмов нет вовсе.

Зачем программисту знать о NP-полных задачах? Если для некоторой задачи удается доказать её NP-полноту, есть основания

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

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

В разделе 36.1 мы формализуем понятие задачи и определим класс Р, состоящий из «задач» (или, как говорят, «языков»), разрешимых за полиномиальное время. В разделе 36.2 будет определен класс NP, состоящий из задач, решение которых может быть проверено за полиномиальное время. Вопрос о совпадении этих классов и есть та центральная проблема теории сложности вычислений, о которой мы говорили.

В разделе 36.3 мы введем понятие сводимости за полиномиальное время, дадим определение NP-полной задачи и установим NP-полноту задачи о выполнимости. После этого в разделе 36.4 мы докажем NP-полноту некоторых других задач, сведя к ним задачу о выполнимости. В разделе 36.5 будет доказана NP-полнота ещё нескольких задач.

36.1. Полиномиальное время

Как мы уже говорили, понятие полиномиально разрешимой задачи принято считать уточнением идеи «практически разрешимой» задачи. Чем объясняется такое соглашение?

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

Второй аргумент в пользу рассмотрения класса полиномиальных алгоритмов - тот факт, что объём этого класса не зависит от выбора конкретной модели вычислений (для достаточно широкого класса моделей). Например, класс задач, которые могут быть решены за полиномиальное время на последовательной машине с произвольным доступом (RAM), совпадает с классом задач, полиномиально разрешимых на машинах Тьюринга (определение которых можно найти в книге Хопкрофта и Ульмана [104] или Льюиса и Пападимитриу [139]). Класс будет тем же и для моделей параллельных вычислений, если, конечно, число процессоров полиномиально зависит от длины входа.

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