♯P - ♯P

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

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

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

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

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

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

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

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

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

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

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

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

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

#P есть множество всех функций , такие , что существует многочлен время недетерминирован машин Тьюринга , что для всех , равно числа ветвей приема в графе вычисления «S на .

{\ displaystyle f: \ {0,1 \} ^ {*} \ to \ mathbb {N}}

{\ displaystyle M}

{\ Displaystyle х \ в \ {0,1 \} ^ {*}}

{\ displaystyle f (x)}

{\ displaystyle M}

{\ displaystyle x}

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

#P есть множество функций , таких , что существует многочлен и полиномиального детерминированной машины Тьюринга , называется верификатор, что для каждого , . (Другими словами, равен размеру набора, содержащего все сертификаты полиномиального размера).

{\ displaystyle f: \ {0,1 \} ^ {*} \ to \ mathbb {N}}

{\ Displaystyle p: \ mathbb {N} \ to \ mathbb {N}}

{\ displaystyle V}

{\ Displaystyle х \ в \ {0,1 \} ^ {*}}

{\ Displaystyle е (х) = {\ Big |} {\ big \ {} y \ in \ {0,1 \} ^ {p (| x |)}: V (x, y) = 1 {\ big \}} {\ Big |}}

{\ displaystyle f (x)}

История

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

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