Класс ♯P

(перенаправлено с «Класс Sharp-P»)

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

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

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

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

,

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

ПримечанияПравить

  1. 1998 Gödel Prize. Seinosuke Toda. Дата обращения: 23 января 2012. Архивировано 16 марта 2010 года.
  2. Leslie G. Valiant. The Complexity of Computing the Permanent (англ.) // Theoretical Computer Science[en]. — Elsevier, 1979. — Vol. 8, no. 2. — P. 189—201. — doi:10.1016/0304-3975(79)90044-6.