Изначально сложные и недетерминированные полиномиальные задачи
С помощью анализа алгоритмов и системы обозначений О () мы получаем возможность рассуждать об эффективности конкретного алгоритма. Однако эти методы не позволяют определить, может ли существовать лучший алгоритм для рассматриваемой задачи. В области анализа сложности исследуются задачи, а не алгоритмы. Первая широкая градация в этой области проводится между задачами, которые могут быть решены за время, измеряемое полиномиальным соотношением, и задачами, которые не могут быть решены за время, измеряемое полиномиальным соотношением, независимо от того, какой алгоритм для этого используется. Класс полиномиальных задач (которые могут быть решены за время 0(пк) для некоторого к) обозначается как Р. Эти задачи иногда называют "легкими", поскольку данный класс содержит задачи, имеющие такую продолжительность прогона, как О(1одл) и О (л). Но он содержит и задачи с затратами времени О (л1000 ), поэтому определение "легкий" не следует понимать слишком буквально.
Еще одним важным классом является NP (сокращение от Nondeterministic Polynomial) — класс недетерминированных полиномиальных задач. Задача относится к этому классу, если существует алгоритм, позволяющий выдвинуть гипотезу о возможном решении, а затем проверить правильность этой гипотезы с помощью полиномиальных затрат времени. Идея такого подхода состоит в том, что если бы можно было воспользоваться сколь угодно большим количеством процессоров, чтобы проверить одновременно все гипотезы, или оказаться крайне удачливым и всегда с первого раза находить правильную гипотезу, то NP-трудные задачи стали бы Р-трудными задачами. Одним из самых важных нерешенных вопросов в компьютерных науках является то, будет ли класс NP эквивалентным классу Р, если нельзя воспользоваться бесконечным количеством процессоров или способностью находить правильную гипотезу с первого раза. Большинство специалистов в области компьютерных наук согласны с тем, что РФЫР, иными словами, что задачи NP являются изначально трудными и для них не существует алгоритмов с полиномиальными затратами времени. Но это утверждение так и не было доказано.
Ученые, пытающиеся найти ответ на вопрос о том, эквивалентны ли классы Р и NP, выделили подкласс класса NP, называемый NP-полными задачами. В этой формулировке слово "полный" означает "являющийся наиболее ярким представителем" и поэтому указывает на самые трудные задачи из класса NP. Было доказано, что либо все NP-полные задачи принадлежат к классу Р, либо ни одна из них к нему не относится. Таким образом, данный класс представляет определенный теоретический интерес, но он важен также с точки зрения практики, поскольку известно, что многие серьезные задачи являются NP-полными. В качестве примера можно указать задачу установления выполнимости: если дано высказывание пропозициональной логики, то есть ли такой вариант присваивания истинностных значений пропозициональным символам в высказывании, при котором оно становится истинным? Если не произойдет чудо и не совпадут друг с другом классы Р и NP, то нельзя будет найти алгоритм, который позволяет решить все задачи установления выполнимости за полиномиальное время. Но исследователей в области искусственного интеллекта в большей степени интересует то, существуют ли алгоритмы, действующие достаточно эффективно при решении типичных задач, выбранных с помощью заранее заданного распределения; как было показано в главе 7, существуют алгоритмы наподобие WalkSAT, которые действуют вполне успешно при решении многих задач.
Класс ко-NP является комплементарным (дополнительным) по отношению к классу NP; это означает, что для каждой задачи принятия решения из класса NP существует соответствующая задача в классе ко-NP, на которую может быть дан положительный или отрицательный ответ, противоположный ответу на задачу класса NP. Известно, что Р является подмножеством и NP, и ко-NP, кроме того, считается, что к классу ко-NP относятся некоторые задачи, не входящие в класс Р. Такие задачи называются KO-NP-ПОЛНЫМИ и являются самыми трудными задачами в классе ко-NP.
Класс #Р (произносится как "шарп Р", или "диез Р") представляет собой множество задач подсчета количества вариантов, соответствующих задачам принятия решения из класса NP. Задачи принятия решения имеют однозначный (положительный или отрицательный) ответ; примером задачи такого типа является следующая: "Существует ли решение для данной формулы 3-SAT?" Задачи подсчета количества вариантов имеют целочисленный ответ, например: "Сколько решений существует для данной формулы 3-SAT?" В некоторых случаях задача подсчета количества вариантов намного труднее по сравнению с соответствующей задачей принятия решения. Например, принятие решения о том, имеет ли двухдольный граф идеальное паросочетание, может быть выполнено за время О (VE) (где V— количество вершин; Е— количество ребер графа), тогда как задача подсчета того, какое количество идеальных паросочетаний имеется в этом двухдольном графе, является #Р-полной. Это означает, что она не менее трудна, чем любая задача из класса #Р, и поэтому по меньшей мере столь же трудна, как и любая задача NP.
Исследователи определили также класс задач PSPACE; таковыми являются задачи, для которых требуется объем пространства, определяемый полиномиальной зависимостью, даже при их прогоне на недетерминированной машине. Считается, что PSPACE-трудные задачи решаются хуже по сравнению с NP-полными задачами, но не исключено, что в ходе дальнейших исследований может быть установлено, что класс NP эквивалентен классу PSPACE, и также то, что класс Р эквивалентен классу NP.