♯П
-
Определение класса сложности #P
- #P — это набор задач подсчета, связанных с задачами решения в NP.
- Задачи в #P требуют вычисления числа путей недетерминированной машины Тьюринга за полиномиальное время.
-
Отношение к решению задач NP
- Задачи NP часто задают вопрос о существовании решений, удовлетворяющих определенным ограничениям.
- Задачи #P задают вопрос о количестве решений, а не о самом их существовании.
-
Связь с другими классами сложности
- Задачи #P должны быть не менее сложными, чем соответствующие задачи NP.
- Некоторые задачи #P могут быть решены в FP, в то время как другие являются #P-полными.
-
Теорема Тоды и P#P
- Машина с оракулом #P может решать все задачи в PH.
- Для решения задачи в PH требуется всего один запрос к оракулу #P.
-
Примеры задач #P
- Некоторые задачи #P считаются сложными, но соответствуют простым задачам с линейным временем.
-
Формальные определения и история
- #P впервые был определен Лесли Вэлиантом в 1979 году.
- Ларри Стокмейер доказал существование рандомизированного алгоритма для задач #P.
-
Дополнительные ресурсы
- Ссылки на портал компьютерного программирования и статью о взаимосвязи между вычислимостью и сложностью теории.
Полный текст статьи: