Класс ♯P

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

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

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

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

Per ( A ) = ∑ π ∈ S n ∏ i = 1 n a i , π i = ∑ π ∈ S n a 1 , π 1 a 2 , π 2 ⋯ a n , π n {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}}} ,

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