WikiSort.ru - Не сортированное

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

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

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

Известно, что P^#P, класс проблем, решаемых машиной Тьюринга за полиномиальное время с привлечением оракула для класса #P, содержит класс сложности PH^[1]. Исходя из этого, считается, что #P-полные проблемы являются крайне сложными с точки зрения вычислительной сложности.

Известные #P-полные проблемы

Одной из наиболее известных проблем, принадлежащей к классу #P-полных, является проблема вычисления перманента матрицы^[2]:

${\displaystyle {\mbox{Per}}(A)=\sum _{\pi \in S_{n}}\prod _{i=1}^{n}a_{i,\pi _{i}}=\sum _{\pi \in S_{n}}a_{1,\pi _{1}}a_{2,\pi _{2}}\cdots a_{n,\pi _{n}},}$

Для сравнения, на первый взгляд очень похожая проблема вычисления детерминанта матрицы

${\displaystyle {\mbox{det}}(A)=\sum _{\pi \in S_{n}}\operatorname {sgn} (\pi )\prod _{i=1}^{n}a_{i,\pi _{i}}=\sum _{\pi \in S_{n}}\operatorname {sgn} (\pi )a_{1,\pi _{1}}a_{2,\pi _{2}}\cdots a_{n,\pi _{n}},}$

решается за полиномиальное время.

Ссылки

Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.