1. Алгоритмически неразрешимые задачи (нерешаемые задачи). Это задачи, для решения которых не существует алгоритма. Например, доказано, что задача определения, остановится или нет на машине Тьюринга заданная программа, является алгоритмически неразрешимой. В этой книге мы не будем обсуждать задачи из этого класса.
2. Труднорешаемые задачи (вероятно, сложные задачи). Это задачи, для решения которых, по-видимому, не существует полиномиального алгоритма. Иными словами, для их решения, скорее всего, существуют только экспоненциальные алгоритмы.
3. NP-задачи (NP — аббревиатура для «недетерминированные полиномиальные»). Это класс задач, которые мы можем решить за полиномиальное время, если угадаем, какой путь вычислений необходимо выполнить. Грубо говоря, этот класс включает в себя все задачи, которые имеют экспоненциальный алгоритм, но не доказано, что они не могут иметь полиномиального алгоритма.
4. Р-задачи (Р — аббревиатура для «полиномиальный»). Этот класс включает в себя задачи, которые имеют полиномиальные алгоритмы. Большинство людей считают, что этот класс является собственным подклассом класса 3.
Все задачи, для которых есть полиномиальные алгоритмы, составляют класс Р. Например, задачи, требующие nlogn единиц времени или n116+3n4+ 7739 единиц времени, принадлежат этому классу. Сама единица времени не фиксирована. Ею может быть, например, микросекунда или час.
Особенности класса Р:
1) сумма и произведение многочленов являются многочленами и поэтому суперпозиция многочленов есть тоже многочлен. Следовательно, легко определить, является ли алгоритм полиномиальным или нет.
2) полиномиальная функция не чувствительна к особенностям реализации. Реализация алгоритма с использованием другой структуры данных может понизить степень многочлена, но не найдено примера двух реализаций одного алгоритма, одна из которых требует полиномиального, а другая — экпоненциального времени.
3) полиномиальные алгоритмы быстрее экспоненциальных, когда задача приобретает большие размеры. Рассмотрим алгоритмы А и В. Алгоритм А требует n5 операций, а алгоритм В требует 2n операций. Если каждая операция выполняется за микросекунду, то алгоритм А при п = 10 закончит свою работу за 0.1с., а при п = 60 — за 13 мин. С другой стороны, алгоритм А при n = 10 закончит свою работу за 0.001с., а при п = 60 — за 366 веков. По этой причине Эдмондс назвал полиномиальные алгоритмы хорошими. Даже если при малых значениях п полиномиальный алгоритм медленнее экспоненциального, при больших п он превосходит по скорости работы экспоненциальный. Заметим, что это справедливо только для худшего случая. Существуют экспоненциальные алгоритмы, которые в среднем быстрее полиномиальных.
Можно не разбивать класс Р на подклассы, такие, как n, nlogn, n3 и т.д., и использовать нотацию «О большое», не беспокоясь о коэффициенте, стоящем перед функцией.
Рассмотрим задачу определения, есть ли в графе эйлеровы циклы. Граф имеет эйлеровы циклы тогда и только тогда, когда
(i) граф связен,
(ii) (ii) степень каждой вершины четна.
Мы не будем доказывать, что эти условия необходимы и достаточны, а только оценим объем работы, необходимой для проверки этих двух условий.
Предположим, что граф задан пхn матрицей, в которой элемент i-ой строки j-ro столбца равен 1, если i-ая вершина смежна j-ой вершине, и 0 в противном случае. (Для наших целей определим элементы на диагонали равными 0.) Чтобы проверить, все ли вершины имеют четную степень, сложим элементы каждой строки и проверим, будут ли суммы четными. Так как в графе n вершин, то таких сумм будет п. Если просмотр каждого элемента выполняется за одну операцию, то всего требуется n2 операций. Итак, для проверки четности вершин требуется полиномиальное время. Чтобы проверить, является ли граф связным, предположим, что граф задан списком смежности, т. е. списком вершин вместе с соседями, указанными для каждой вершины. По известной матрице смежности можно построить список смежности за время О(n2). Затем, используя поиск в глубину, проверить граф на связность. Так как каждая дуга будет пройдена по крайней мере два раза (ровно два раза, если дуга принадлежит остовному дереву, и один раз, если она не принадлежит ему), то алгоритм требует О(т + n), где т — число дуг. Получаем полиномиальный алгоритм в терминах числа вершин п. Подчеркнем, что в данном случае алгоритм выдает ответ «да», если граф имеет эйлеров цикл, или «нет», если эйлерова цикла в графе нет.
Обычно задачу формулируют так, что возможными ответами являются «да» или «нет». Например, задачу коммивояжера нахождения кратчайшего цикла в графе можно переформулировать следующим образом.
Имеется ли в графе цикл, длина которого меньше заданного числа В? Если при любом В на этот вопрос можно ответить за полиномиальное время, то легко за полиномиальное время решить задачу коммивояжера. (Легко установить верхнюю и нижнюю границу для кратчайшего цикла, а затем использовать бинарный поиск, испытывая разные В).
Далее предполагается, что рассматриваются только задачи с ответами «да» или «нет». Такие задачи называются задачами распознавания, в то время как задачи максимизации или минимизации называются задачами оптимизации, для нихтермины соответственно NP-полные и NP-трудные задачи.
Рассмотрим алгоритм как компьютерную программу. При заданных входных данных программа выполняет различные вычисления. В зависимости от промежуточных результатов программа выполняет другие вычисления до тех пор, пока не будет получен ответ. Для задач распознавания таким ответом является «да» или «нет».
Представим весь процесс вычислений в виде корневого дерева, каждая вершина представляет некоторое вычисление, а листьям приписаны возможные ответы «да» и «нет».
Для того, чтобы алгоритм был полиномиальным, дерево должно иметь полиномиальную высоту и, кроме этого, время, затрачиваемое на вычисления в каждом узле, также должно быть полиномиальным.
Когда входные данные алгоритма известны, компьютерная программа выполняет некоторые вычисления, по результату этих вычислений определяется дальнейший путь вычислений. Полиномиальные алгоритмы обладают тем свойством, что каждую траекторию вычислений можно пройти за полиномиальное время.
Последнее свойство полиномиальных алгоритмов весьма обременительно. Например, для задач теории графов некоторый алгоритм может использовать полиномиальное время, если граф планарный, и экспоненциальное время в противном случае. Представляется весьма важным выделение полиномиальных подклассов в задачах, которые в общей постановке требуют экспоненциального времени. Кроме того, для задач из класса Р построение более эффективных алгоритмов или новых модификаций старых алгоритмов может снизить время работы программы, например, с n3 до n2, n2 до nlogn.
