Класс ♯P

Правильный заголовок этой статьи — Класс #P. Он показан некорректно из-за технических ограничений.

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

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

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

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

$\text{Per}(A)=\underset{\mathrm{\pi <!--\; \pi \; -->}\in <!--\; \in \; -->S_n}{\sum <!--\; \sum \; -->}\underset{i=1}{\overset{n}{\prod <!--\; \prod \; -->}}{a}_{i,{\mathrm{\pi <!--\; \pi \; -->}}_i}=\underset{\mathrm{\pi <!--\; \pi \; -->}\in <!--\; \in \; -->S_n}{\sum <!--\; \sum \; -->}{a}_{1,{\mathrm{\pi <!--\; \pi \; -->}}_1}{a}_{2,{\mathrm{\pi <!--\; \pi \; -->}}_2}\cdots <!--\; \cdots \; -->a_{n,{\mathrm{\pi <!--\; \pi \; -->}}_n}$${\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}}$,

при этом сходная на первый взгляд проблема вычисления детерминанта матрицы решается за полиномиальное время.