Existe um algoritmo polinomial fácil para decidir se existe um caminho entre dois nós em um gráfico direcionado (basta fazer uma travessia rotineira de um gráfico com, digamos, a primeira pesquisa de profundidade).
No entanto, parece que, surpreendentemente, o problema fica muito mais difícil se, em vez de testar a existência, queremos contar o número de caminhos.
Se permitirmos que os caminhos reutilizem os vértices, existe uma solução de programação dinâmica para encontrar o número de caminhos de s a t com n arestas. No entanto, se permitirmos apenas caminhos simples, que não reutilizem vértices, a única solução que posso pensar é a enumeração de caminhos por força bruta , algo que tem complexidade de tempo exponencial.
Então eu pergunto,
- Contar o número de caminhos simples entre dois vértices é difícil?
- Se sim, é um tipo de NP completo? (Eu digo mais ou menos porque tecnicamente não é um problema de decisão ...)
- Existem outros problemas em P que também possuem versões difíceis de contagem assim? **
Respostas:
A classe de complexidade mais comum associada aos problemas de contagem é #P . Decidir se existe um caminho simples de um nó para outro está claramente no NP. Contá-los é então em #P.
Sobre a completude do NP: mesmo que isso não seja um problema de decisão, dificilmente caberia ao NP: pode havercaminhos e o não-determinismo não o ajudam nisso (você ainda precisará verificar todos eles)n !
A resposta para suas duas primeiras duas perguntas é: sim, é difícil, é # P-complete (ref) .
O artigo da Wikipedia fornece fatos pertinentes: 1) algoritmos probabilísticos são úteis para aproximar as funções # P-complete, e esse é o tipo de algoritmo usado para a aproximação no artigo anterior. 2) Há outros problemas fáceis nas versões de contagem difícil (# P-complete):
Você já sabe que, se você remover a restrição "caminho simples", o problema cai em P (bem, você deve limitar o comprimento dos caminhos por um polinômio do tamanho do gráfico ou fornecer o limite como unário)
fonte