#

Vamos ser algum problema de contagem, que é conhecido por ser # P -Complete .$\Pi$$P$

Isso implica que é A P X- difícil (ou seja, não existe PTAS para o problema, a menos que P = N P )?$\Pi$$APX$$P=NP$

Não. Contar conjuntos independentes no gráfico é # P- difícil, mesmo para gráficos regulares, mas Dror Weitz forneceu um PTAS para contar conjuntos independentes de gráficos regulares para qualquer d ≤ 5 [3]. (No modelo sobre o qual ele escreve, contar conjuntos independentes corresponde a tomar λ = 1. )$d$$d\leq5$$\lambda=1$

Computar a permanente de uma matriz 0-1 também é #P -hard (este é o artigo #P original da Valiant [2]), mas, relaxando um pouco seus requisitos, há um FPRAS devido a Jerrum e Sinclair [1]. Isso corresponde à contagem de combinações perfeitas em gráficos bipartidos.

Referências

[1] Mark Jerrum e Alistair Sinclair, "Aproximando a permanente". SIAM Journal on Computing , 18 (6): 1149-1178, 1989. ( PDF )

[2] Leslie Valiant, "A complexidade de computar o permanente". Ciência da Computação Teórica , 8: 189–201, 1979. ( PDF )

[3] Dror Weitz, "Contando conjuntos independentes até o limiar da árvore". STOC 2006. (Versão completa não publicada: PDF .)

Adicionando outro exemplo, me deparei com um resultado ainda mais forte:

$\#P$