♯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 на . ^[1]

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

{\ displaystyle M}

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

{\ displaystyle f (x)}

{\ displaystyle M}

{\ displaystyle x}

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

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

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

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

{\ displaystyle V}

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

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

f(x)

История [ править ]

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

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

См. Также [ править ]

Квантовые вычисления

Ссылки [ править ]

^ а б Варак, Вооз (весна 2006 г.). «Сложность подсчета» (PDF) . Компьютерные науки 522: вычислительная сложность . Университет Принстона.
^ Арора, Санджив ; Варак, Вооз (2009). Вычислительная сложность: современный подход . Издательство Кембриджского университета. п. 344. ISBN 978-0-521-42426-4.
↑ Лесли Г. Валиант (1979). «Сложность вычисления постоянного». Теоретическая информатика . Эльзевир . 8 (2): 189–201. DOI : 10.1016 / 0304-3975 (79) 90044-6 .
^ Stockmeyer Ларри (ноябрь 1985). «Об алгоритмах аппроксимации для #P» (PDF) . SIAM Journal on Computing . 14 (4): 849. DOI : 10,1137 / 0214060 . Архивировано из оригинала (PDF) на 2009 резюме Lay .

Внешние ссылки [ править ]

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

[Barak-Counting-1] а б Варак, Вооз (весна 2006 г.). «Сложность подсчета» (PDF) . Компьютерные науки 522: вычислительная сложность . Университет Принстона.

[2] Арора, Санджив ; Варак, Вооз (2009). Вычислительная сложность: современный подход . Издательство Кембриджского университета. п. 344. ISBN 978-0-521-42426-4.

[3] Лесли Г. Валиант (1979). «Сложность вычисления постоянного». Теоретическая информатика . Эльзевир . 8 (2): 189–201. DOI : 10.1016 / 0304-3975 (79) 90044-6 .

[4] Stockmeyer Ларри (ноябрь 1985). «Об алгоритмах аппроксимации для #P» (PDF) . SIAM Journal on Computing . 14 (4): 849. DOI : 10,1137 / 0214060 . Архивировано из оригинала (PDF) на 2009 резюме Lay .

[1]

vтеВажные классы сложности ( подробнее )
Считается выполнимым	DLOGTIME AC 0 АКК 0 ТК 0 L SL RL NL NC SC CC п P-полный ЗПП RP BPP BQP APX
Подозреваемый невыполнимый	ВВЕРХ НП НП-полный NP-жесткий со-НП совместно NP-полный ЯВЛЯЮСЬ QMA PH ⊕P ПП #П # P-complete IP PSPACE PSPACE-полный
Считается невозможным	EXPTIME СЛЕДУЮЩИЙ ВРЕМЯ EXPSPACE 2-ВРЕМЯ НАЧАЛЬНЫЙ PR р RE ВСЕ
Иерархии классов	Полиномиальная иерархия Экспоненциальная иерархия Иерархия Гжегорчика Арифметическая иерархия Логическая иерархия
Семьи классов	DTIME NTIME DSPACE NSPACE Вероятностно проверяемое доказательство Интерактивная система доказательств