Существует простой полиномиальный алгоритм, позволяющий определить, существует ли путь между двумя узлами в ориентированном графе (просто выполните обычный обход графа с, скажем, поиском по глубине).
Однако, на удивление, проблема становится намного сложнее, если вместо проверки существования мы хотим посчитать количество путей.
Если мы разрешаем путям повторно использовать вершины, то существует динамическое программное решение, позволяющее найти число путей от s до t с n ребрами. Однако, если мы разрешаем только простые пути, которые не используют вершины, единственное решение, которое я могу придумать, - это перечисление путей методом грубой силы , что имеет экспоненциальную временную сложность.
Поэтому я спрашиваю,
- Трудно ли считать число простых путей между двумя вершинами?
- Если так, то это своего рода NP-полный? (Я говорю вроде как, потому что технически это не проблема решения ...)
- Есть ли другие проблемы в P, у которых есть версии с таким же жестким подсчетом? **
Ответы:
Наиболее распространенным классом сложности, связанным с подсчетом проблем, является #P . Решение о том, существует ли простой путь от данного узла к другому, находится в NP. Подсчет их тогда в #P.
Ответ на два первых двух вопроса: да, это сложно, это # P-complete (ref) .
Статья Википедии дает соответствующие факты: 1) вероятностные алгоритмы полезны для аппроксимации # P-полных функций, и именно такой алгоритм использовался для аппроксимации в предыдущей статье. 2) Есть другие простые проблемы с жесткими (# P-complete) версиями подсчета:
Вы уже знаете, что если вы удалите ограничение «простой путь», проблема попадет в P (ну, вы должны ограничить длину путей полиномом от размера графа или дать оценку в унарном)
источник