Класс Sharp-P

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

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

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

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

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

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

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

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

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

Ссылки[править | править вики-текст]

  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.