♯P - ♯P

Na teoria da complexidade computacional , a classe de complexidade #P (pronuncia-se "P acentuado" ou, às vezes "número P" ou "hash P") é o conjunto dos problemas de contagem associados aos problemas de decisão no conjunto NP . Mais formalmente, #P é a classe de problemas de função da forma "compute f ( x )", onde f é 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 conhecidas, não é uma classe de problemas de decisão, mas uma classe de problemas de função . Os problemas mais difíceis e representativos desta classe são # P-completos .

Relação com problemas de decisão

Um problema de decisão NP geralmente tem a forma "Há alguma solução que satisfaça certas restrições?" Por exemplo:

• Existem subconjuntos de uma lista de inteiros que somam zero? ( problema de soma de subconjunto )
• Existe algum ciclo hamiltoniano em um determinado gráfico com custo inferior a 100? ( problema do caixeiro viajante )
• Existem atribuições de variáveis ​​que satisfazem uma dada fórmula CNF (forma normal conjuntiva) ? ( Problema de satisfatibilidade booleana ou SAT)
• Um polinômio real univariado tem raízes positivas? ( Descoberta de raiz )

Os problemas de função #P correspondentes perguntam "quantos" em vez de "há algum". Por exemplo:

• Quantos subconjuntos de uma lista de inteiros somam zero?
• Quantos ciclos hamiltonianos em um determinado gráfico custaram menos de 100?
• Quantas atribuições de variáveis ​​satisfazem uma determinada fórmula CNF?
• Quantas raízes de um polinômio real univariado são positivas?

Classes de complexidade relacionadas

Claramente, um problema #P deve ser pelo menos tão difícil quanto o problema NP correspondente . Se for fácil contar as respostas, então deve ser fácil saber se há alguma resposta - basta contá-las e ver se a contagem é maior que zero. Alguns desses problemas, como localização de raiz , são fáceis o suficiente para estar no FP , enquanto outros são # P-completos .

Uma consequência do teorema de Toda é que uma máquina de tempo polinomial com um oráculo #P ( P ^#P ) pode resolver todos os problemas em PH , toda a hierarquia polinomial . Na verdade, a máquina do tempo polinomial só precisa fazer uma consulta #P para resolver qualquer problema em PH . Isso é uma indicação da extrema dificuldade de resolver problemas #P -completos com exatidão.

Surpreendentemente, alguns problemas #P considerados difíceis correspondem a problemas P fáceis (por exemplo, de tempo linear) . Para obter mais informações sobre isso, consulte # P-complete .

A classe de problema de decisão mais próxima de #P é PP , que pergunta se a maioria (mais da metade) dos caminhos de computação aceita. Isso encontra o bit mais significativo na resposta do problema #P . A classe de problema de decisão ⊕P (pronuncia-se "Paridade-P") ao invés pede o bit menos significativo da resposta #P .

Definições formais

#P é formalmente definido da seguinte forma:

#P é o conjunto de todas as funções tal que existe uma máquina de Turing não determinística de tempo polinomial tal que, para todos , é igual ao número de ramos aceitáveis ​​no gráfico de computação de .${\ displaystyle f: \ {0,1 \} ^ {*} \ to \ mathbb {N}}$ ${\ displaystyle M}$${\ displaystyle x \ in \ {0,1 \} ^ {*}}$${\ displaystyle f (x)}$${\ displaystyle M}$${\ displaystyle x}$

#P também pode ser definido de forma equivalente em termos de um verificador. Um problema de decisão está em NP se existe um certificado verificável em tempo polinomial para uma determinada instância de problema - isto é, NP pergunta se existe uma prova de associação para a entrada que pode ser verificada quanto à exatidão em tempo polinomial. A classe #P pergunta quantos certificados existem para uma instância de problema que pode ser verificada quanto à exatidão em tempo polinomial. Neste contexto, #P é definido da seguinte forma:

#P é o conjunto de funções de tal modo que existe um polinomial e um tempo polinomial máquina de Turing determinista , chamado o verificador, de tal modo que para cada , . (Em outras palavras, é igual ao tamanho do conjunto contendo todos os certificados de tamanho polinomial).${\ displaystyle f: \ {0,1 \} ^ {*} \ to \ mathbb {N}}$${\ displaystyle p: \ mathbb {N} \ to \ mathbb {N}}$ ${\ displaystyle V}$${\ displaystyle x \ in \ {0,1 \} ^ {*}}$${\ displaystyle f (x) = {\ Big |} {\ big \ {} y \ in \ {0,1 \} ^ {p (| x |)}: V (x, y) = 1 {\ big \}} {\ Big |}}$${\ displaystyle f (x)}$

História

A classe de complexidade #P foi definida pela primeira vez por Leslie Valiant em um artigo de 1979 sobre o cálculo da permanente de uma matriz quadrada , no qual ele provou que a permanente é # P-completa .

Larry Stockmeyer provou que para cada problema #P existe um algoritmo aleatório usando um oráculo para SAT, que fornece uma instância de e retorna com alta probabilidade um número como esse . O tempo de execução do algoritmo é polinomial em e . O algoritmo é baseado no lema de hash restante . ${\ displaystyle P}$${\ displaystyle a}$${\ displaystyle P}$${\ displaystyle \ epsilon> 0}$${\ displaystyle x}$${\ displaystyle (1- \ epsilon) P (a) \ leq x \ leq (1+ \ epsilon) P (a)}$${\ displaystyle a}$${\ displaystyle 1 / \ epsilon}$

Veja também

• Computação quântica  - Estudo de um modelo de computação

Referências

links externos

• Zoo de Complexidade : Classe #P