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 . 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 ? * 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? 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.