♯P

В теории сложности вычислений класс сложности #P (произносится как «острый P» или иногда «число P» или «хэш P») представляет собой набор задач подсчета , связанных с проблемами решения в множестве NP . Более формально, #P — это класс функциональных задач вида «вычислить f ( x )», где f — количество принимающих путей недетерминированной машины Тьюринга, работающей за полиномиальное время . В отличие от большинства известных классов сложности, это не класс задач принятия решений , а класс функциональных задач . Наиболее сложные и репрезентативные задачи этого класса — #P-полные .

Отношение к

Проблема принятия решения NP часто имеет вид: «Существуют ли какие-либо решения, удовлетворяющие определенным ограничениям?» Например:

• Существуют ли в списке целых чисел подмножества, сумма которых равна нулю? ( проблема с суммой подмножества )
• Существуют ли гамильтоновы циклы в данном графе со стоимостью меньше 100? ( задача коммивояжера )
• Существуют ли какие-либо назначения переменных, удовлетворяющие заданной формуле КНФ (конъюнктивной нормальной формы) ? ( булева проблема выполнимости или SAT)
• Имеет ли одномерный действительный многочлен положительные корни? ( нахождение корня )

Соответствующие задачи с функцией #P спрашивают «сколько», а не «есть ли они?». Например:

• Сколько подмножеств списка целых чисел в сумме дает ноль?
• Сколько гамильтоновых циклов в данном графе стоили меньше 100?
• Сколько назначений переменных удовлетворяют данной формуле CNF?
• Сколько корней вещественного одномерного многочлена являются положительными?

Связанные классы сложности

Очевидно, что задача #P должна быть по крайней мере такой же сложной, как и соответствующая задача NP . Если подсчитать ответы легко, то должно быть легко и определить, есть ли ответы — просто подсчитайте их и посмотрите, больше ли число нуля. Некоторые из этих задач, такие как поиск корня , достаточно просты для решения FP , тогда как другие являются #P-полными .

Одним из следствий теоремы Тоды является то, что машина полиномиального времени с #P оракулом ( P ^#П ) может решить все проблемы в PH , всю полиномиальную иерархию . Фактически, машине полиномиального времени достаточно выполнить только один #P -запрос, чтобы решить любую задачу в PH . Это указывает на крайнюю трудность точного решения #P -полных задач.

Удивительно, но некоторые #P -задачи, которые считаются сложными, соответствуют простым (например, с линейным временем) P- задачам. Дополнительную информацию об этом см. в разделе #P-complete .

Ближайшим классом проблем принятия решений к #P является PP , который спрашивает, приемлемо ли большинство (более половины) путей вычислений. Это позволит найти самый значимый бит в ответе на задачу #P . Класс проблемы принятия решения ⊕P (произносится как «Четность-P») вместо этого запрашивает младший бит ответа #P .

Формальные определения

#P формально определяется следующим образом:

#P — набор всех функций $f:\{0,1\}^{*}\to \mathbb {N}$ такая, что существует недетерминированная машина Тьюринга с полиномиальным временем $M$ такой, что для всех $x\in \{0,1\}^{*}$, $f(x)$ равно количеству принимающих филиалов в $M$график вычислений на $x$.

#P также может быть эквивалентно определен в терминах проверяющего. Проблема решения находится в NP, если существует проверяемый за полиномиальное время сертификат для данного экземпляра проблемы, то есть NP запрашивает, существует ли доказательство принадлежности входных данных, правильность которого можно проверить за полиномиальное время. Класс #P запрашивает, сколько существует сертификатов для экземпляра проблемы, корректность которых можно проверить за полиномиальное время. В этом контексте #P определяется следующим образом:

#P — набор функций $f:\{0,1\}^{*}\to \mathbb {N}$ такой, что существует полином $p:\mathbb {N} \to \mathbb {N}$ с полиномиальным временем и детерминированная машина Тьюринга $V$, называемый верификатором, такой, что для каждого $x\in \{0,1\}^{*}$, $f(x)={\Big |}{\big \{}y\in \{0,1\}^{p(|x|)}:V(x,y)=1{\big \}}{\Big |}$. (Другими словами, $f(x)$ равен размеру набора, содержащего все сертификаты полиномиального размера).

История

Класс сложности #P был впервые определен Лесли Валиантом в статье 1979 года о вычислении перманента квадратной матрицы , в которой он доказал, что перманент является #P-полным .

Ларри Стокмейер доказал, что для каждой задачи #P $P$ существует рандомизированный алгоритм , использующий оракул для SAT, который в данном случае $a$ из $P$ и $\epsilon >0$ возвращает с высокой вероятностью число $x$ такой, что $(1-\epsilon )P(a)\leq x\leq (1+\epsilon )P(a)$. Время работы алгоритма является полиномиальным по $a$ и $1/\epsilon$. Алгоритм основан на лемме об остаточном хеше .

См. также

• Quantum_computing#Relation_to_computability_and_complexity_theory – Технология, использующая квантовую механику.

Внешние ссылки

• Зоопарк сложности : класс #P