Класс 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.

Классы сложности алгоритмов

 

Cчитаются лёгкими	P • L • NL • AC • NC • P-complete • BQP • BPP • RP • ZPP
Предпологаются сложными	NP (co-NP • NP-complete • co-NP-complete ) • UP • #P (#P-complete ) • IP • PSPACE (PSPACE-complete) • R • PP • AM
Cчитаются сложными	EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH
Список алгоритмов

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