Класс Sharp-P

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Правильный заголовок этой статьи — Класс #P. Он показан некорректно из-за технических ограничений.

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

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

Связь с известными классами сложности[править | править исходный текст]

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

Известные #P-полные проблемы[править | править исходный текст]

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

\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},

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

\mbox{det}(A) = \sum_{\pi \in S_n} \sgn(\pi) \prod_{i=1}^n a_{i, \pi_i} = \sum_{\pi \in S_n} \sgn(\pi) a_{1, \pi_1} a_{2, \pi_2} \cdots a_{n, \pi_n},

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

Ссылки[править | править исходный текст]

  1. 1998 Gödel Prize. Seinosuke Toda
  2. Leslie G. Valiant (1979). «The Complexity of Computing the Permanent». Theoretical Computer Science (Elsevier) 8 (2): 189–201. DOI:10.1016/0304-3975(79)90044-6.