Главная arrow книги arrow Копия Приложение А. Математические основы arrow Изначально сложные и недетерминированные полиномиальные задачи
Изначально сложные и недетерминированные полиномиальные задачи

Класс #Р (произносится как "шарп Р", или "диез Р") представляет собой множество задач подсчета количества вариантов, соответствующих задачам принятия решения из класса NP. Задачи принятия решения имеют однозначный (положительный или отрицательный) ответ; примером задачи такого типа является следующая: "Существует ли решение для данной формулы 3-SAT?" Задачи подсчета количества вариантов имеют целочисленный ответ, например: "Сколько решений существует для данной формулы 3-SAT?" В некоторых случаях задача подсчета количества вариантов намного труднее по сравнению с соответствующей задачей принятия решения. Например, принятие решения о том, имеет ли двухдольный граф идеальное паросочетание, может быть выполнено за время O(VE) (где V— количество вершин; Е— количество ребер графа), тогда как задача подсчета того, какое количество идеальных паросочетаний имеется в этом двухдольном графе, является #Р-полной. Это означает, что она не менее трудна, чем любая задача из класса #Р, и поэтому по меньшей мере столь же трудна, как и любая задача NP.

Исследователи определили также класс задач PSPACE; таковыми являются задачи, для которых требуется объем пространства, определяемый полиномиальной зависимостью, даже при их прогоне на недетерминированной машине. Считается, что PSPACE-трудные задачи решаются хуже по сравнению с NP-полными задачами, но не исключено, что в ходе дальнейших исследований может быть установлено, что класс NP эквивалентен классу PSPACE, и также то, что класс Р эквивалентен классу NP.