Na teoria da complexidade computacional, a classe de complexidade ♯P (pronunciada em inglês como number P, sharp P ou hash P) é o conjunto dos problemas de contagem associado aos problemas de decisão pertencentes ao conjunto NP. Mais formalmente, ♯P é a classe de problemas onde a função é da forma: "compute ƒ(x)", onde ƒ é o número de caminhos de aceitação de uma máquina de Turing não-determinística rodando em tempo polinomial. Ao contrário da maioria das classes de complexidade, não é uma classe de problemas de decisão, mas uma classe de problemas de função.
Um problema em NP é geralmente da forma: "Existe alguma solução que satisfaça certas restrições?". Por exemplo: Existe algum subconjunto de uma lista de inteiros cujo resultado da soma do subconjunto é zero? (Problema da soma dos subconjuntos) Existem ciclos Hamiltonianos em um determinado grafo com custo menor do que 100? (problema do caixeiro viajante) Existem quaisquer atribuições de variáveis que satisfazem uma dada fórmula na Forma Normal Conjuntiva? (Problema da Satisfatibilidade booleana) Os problemas correspondentes em ♯P são da forma: '"quantas soluções existem?'" ao invés de "Existe alguma solução?". Por exemplo: Existem quantos subconjuntos de uma lista de inteiros cuja soma é igual a zero? Quantos ciclos Hamiltonianos em um determinado grafo custam menos do que 100? Quantas atribuições de variáveis são capazes de satisfazer uma fórmula na Forma Normal Conjuntiva? Claramente, um problema da classe ♯P deve ser pelo menos tão difícil quanto o problema NP correspondente. Se é fácil realizar a contagem de soluções, logo, é fácil de dizer se existem quaisquer soluções – apenas contá-las e verificar se a soma delas é maior que zero.
Uma consequência do Teorema de Toda é que uma máquina de tempo polinomial com uma Máquina oráculo ♯P (P♯P) pode resolver todos os problemas em PH, toda a Hierarquia Polinomial. Na verdade, a máquina de tempo polinomial só precisa fazer uma consulta ♯P para resolver qualquer problema em PH. Este é um indício da extrema dificuldade de se resover problemas ♯P-completos exatamente.
Surpreendentemente, alguns problemas ♯P que se acredita serem difíceis correspondem a problemas simples em P. Para obter mais informações sobre isso, consulte P-Sharp-Completude.
A classe de problemas de decisão mais próxima de ♯P é a PP, que pergunta se uma maioria dos ramos de computação (mais da metade) são aceitos. Ele encontra o bit mais significativo da resposta do problema em ♯P. O problema de decisão de classe ⊕P, em vez disso, pergunta qual o bit menos significativo da resposta do problema em ♯P.
A classe de complexidade ♯P foi definida primeiramente por Leslie Valiant em 1979, com um artigo sobre a computação do Permanente, na qual ele provou que Permanente é ♯P-Completo.
Larry Stockmeyer provou que para todo problema P em ♯P , existe um algoritmo randômico utilizando uma máquina oráculo para SAT, que, dada uma instância de P e um ε > 0, retorna, com alta probabilidade, um número x tal que . O tempo de execução do algoritmo é polinomial entre a e 1/ε. O algoritmo é baseado em Lema de sobra de hash.
Referências
Ligações externas A Complexidade Do Zoo: Classe ♯P Código explicado Categoria:Classes de complexidade