P-Sharp

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 é 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 . 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 . 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 .