♯P

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 $(1-\epsilon )P(a)\leq x\leq (1+\epsilon )P(a)$. O tempo de execução do algoritmo é polinomial entre a e 1/ε. O algoritmo é baseado em Lema de sobra de hash.

Ligações externas

• A Complexidade Do Zoo: Classe ♯P
• Código explicado