- Класс Sharp-P
-
- Правильный заголовок этой статьи — Класс #P. Он показан некорректно из-за технических ограничений.
В теории сложности, #P является классом проблем, решением которых является количество успешных, т.е., завершающихся в допускающих состояниях, путей вычислений для некой недетерминированной машины Тьюринга, работающей за полиномиальное время. Например, следующие проблемы принадлежат к #P:
- Сколько различных гамильтоновых циклов существует в данном графе?
- Сколько различных путей между двумя данными вершинами существует в данном графе?
Связь с известными классами сложности
Известно, что P#P, класс проблем, решаемых машиной Тьюринга за полиномиальное время с привлечением оракула для класса #P, содержит класс сложности PH[1]. Исходя из этого, считается, что #P-полные проблемы являются крайне сложными с точки зрения вычислительной сложности.
Известные #P-полные проблемы
Одной из наиболее известных проблем, принадлежащей к классу #P-полных, является проблема вычисления перманента матрицы[2]:
Для сравнения, на первый взгляд очень похожая проблема вычисления детерминанта матрицы
решается за полиномиальное время.
Ссылки
- ↑ 1998 Gödel Prize. Seinosuke Toda
- ↑ 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 Список алгоритмов Для улучшения этой статьи желательно?: - Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
Категория:- Классы сложности
Wikimedia Foundation. 2010.