♯P
Класс сложности

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

Отношение к проблемам принятия решений

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

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

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

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

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

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

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

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

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

#P — это множество всех функций, таких что существует недетерминированная машина Тьюринга с полиномиальным временем, такая что для всех , равно числу принимающих ветвей в графе вычислений на . [1] ф : { 0 , 1 } ∗ → Н {\displaystyle f:\{0,1\}^{*}\to \mathbb {N} } М {\displaystyle М} х ∈ { 0 , 1 } ∗ {\displaystyle x\in \{0,1\}^{*}} ф ( х ) {\displaystyle f(x)} М {\displaystyle М} х {\displaystyle x}

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

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

История

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

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

Смотрите также

Ссылки

  1. ^ ab Barak, Boaz (весна 2006 г.). "Сложность подсчета" (PDF) . Computer Science 522: Computational Complexity . Princeton University.
  2. ^ Арора, Санджив ; Барак, Боаз (2009). Вычислительная сложность: современный подход . Cambridge University Press. стр. 344. ISBN 978-0-521-42426-4.
  3. ^ Лесли Г. Валиант (1979). «Сложность вычисления постоянного». Теоретическая информатика . 8 (2). Elsevier : 189– 201. doi : 10.1016/0304-3975(79)90044-6 .
  4. ^ Стокмейер, Ларри (ноябрь 1985 г.). «О приближенных алгоритмах для #P» (PDF) . SIAM Journal on Computing . 14 (4): 849– 861. doi :10.1137/0214060. Архивировано из оригинала (PDF) 28 октября 2009 г.
Взято с "https://en.wikipedia.org/w/index.php?title=♯P&oldid=1270029896"