P-Sharp completude
#P-completo, pronunciado "P-sharp completo" ou "P-número completo" é uma classe de complexidade na teoria da complexidade computacional. Por definição, um problema é #P-completo se, e somente se, ele está em #P, e todo problema em #P pode ser reduzido a ele por uma redução de contagem de tempo polinomial, isto é, uma Redução em tempo polinomial relativas às Cardinalidades dos conjuntos de solução. Equivalentemente, um problema é #P-completo se, e somente se, ele está em #P, e, para qualquer máquina de Turing não determinística, o problema de computar o número de ramos de aceitação pode ser reduzido para este problema.
Exemplos de problemas #P-completos incluem:
- Quantas diferentes atribuições de variáveis irão satisfazer uma determinada fórmula booleana genérica? (Sharp SAT)
- Quantas diferentes atribuições de variáveis irão satisfazer uma determinada fórmula DNF?
- Quantas diferentes atribuições de variáveis irão satisfazer uma determinada fórmula 2-satisfatibilidade?
- Quantos Acoplamentos existem para um determinado grafo bipartido?
- Qual é o valor permanente de uma dada matriz cujas entradas são 0 ou 1? (Consulte Permanente é P-Sharp-completo.)
- Quantas Colorações de grafo usando k cores existem para um determinado grafo G?
- Quantas extensões lineares diferentes existem para uma dada ordem parcial, ou, equivalentemente, quantas ordenações topológicas diferentes existem em um determinado grafo acíclico direcionado?[1]
Um algoritmo em tempo polinomial para resolver um problema #P-completo, se é que existe, implicaria em que P = NP, e, portanto, P = PH. No entanto, nenhum algoritmo como esse é conhecido atualmente.
Problemas fáceis com versões difíceis de contagem editar
É surpreendente que alguns problemas #P-completos correspondem a problemas fáceis de P. É muito fácil determinar a satisfatibilidade de uma fórmula booleana na FND: uma fórmula é satisfatível se e somente se ela contém uma conjunção satisfatível (uma que não contenha uma variável e a sua negação), considerando que a contagem da quantidade de atribuições satisfeitoras é #P-completo. Também é fácil decidir 2-SAT, em contraste com contar a quantidade de atribuições satisfeitoras. Ordenação topológica é fácil, em contraste com contar a quantidade de ordenações topológicas. A mesma observação pode ser feita para o problema da correspondência perfeita. Sabia-se antes que o problema de decisão: "existe uma correspondência perfeita para um dado grafo bipartido?" pode ser resolvido em tempo polinomial, e na verdade, para um grafo com V vértices e E arestas, ele pode ser resolvido em tempo O(VE). A pergunta correspondente: "Quantas correspondências perfeitas um dado grafo bipartido tem?" já é #P-completa. O problema da contagem da quantidade de conexões perfeitas (ou em grafos direcionados: o número de vértices do subciclo do grafo) é conhecido por ser equivalente ao problema do cálculo do permanente de uma matriz. O problema da contagem de conexões perfeitas foi o primeiro problema de contagem correspondente a um problema P fácil a ser demonstrado #P-completo, em um artigo de 1979 de Leslie Valiant, que também definiu as classes #P e #P-completo pela primeira vez.[2]
Aproximação editar
Existem algoritmos probabilísticos que retornam boas aproximações para alguns problemas #P-completos com alta probabilidade. Esta é uma das demonstrações de poder dos algoritmos probabilísticos.
Muitos problemas #P-completos possuem um esquema de aproximação randômico de tempo polinomial, ou "FPRAS", que, informalmente, irá produzir com alta probabilidade uma aproximação com um grau arbitrário de precisão, em tempo polinomial com relação tanto ao tamanho do problema como o grau de precisão exigido. Jerrum, Valiant, e Vazirani mostraram que todo problema #P-completo ou tem uma FPRAS, ou é essencialmente impossível de se aproximar; se existir qualquer algoritmo em tempo polinomial que consistentemente produza uma aproximação de um problema #P-completo que está em uma relação polinomial de tamanho da entrada da resposta exata, então tal algoritmo pode ser usado para construir um FPRAS.[3]
Referências
- ↑ Brightwell, Graham R.; Winkler, Peter (1991). «Counting linear extensions». Order. 8 (3): 225–242. doi:10.1007/BF00383444
- ↑ Leslie G. Valiant (1979). «The Complexity of Computing the Permanent». Elsevier. Theoretical Computer Science. 8 (2): 189–201. doi:10.1016/0304-3975(79)90044-6
- ↑ Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). «Random Generation of Combinatorial Structures from a Uniform Distribution». Elsevier. Theoretical Computer Science. 43: 169–188. doi:10.1016/0304-3975(86)90174-x
Leituras Sugeridas editar
- Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8