В теории сложности, #P является классом проблем, решением которых является количество успешных, то есть, завершающихся в допускающих состояниях, путей вычислений для некой недетерминированной машины Тьюринга, работающей за полиномиальное время. Например, следующие проблемы принадлежат к #P:
Известно, что P#P, класс проблем, решаемых машиной Тьюринга за полиномиальное время с привлечением оракула для класса #P, содержит класс сложности PH[1]. Исходя из этого, считается, что #P-полные проблемы являются крайне сложными с точки зрения вычислительной сложности.
Одной из наиболее известных проблем, принадлежащей к классу #P-полных, является проблема вычисления перманента матрицы[2]:
Для сравнения, на первый взгляд очень похожая проблема вычисления детерминанта матрицы
решается за полиномиальное время.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .