¿# Completitud implica dureza de aproximación?

Sea un problema de conteo que se sabe que es # -Complete .$\Pi$$P$

¿ Implica que es duro (es decir, no existe PTAS para el problema a menos que )?$\Pi$$APX$$P=NP$

No. Contando conjuntos independientes en el gráfico es #P -difícil, incluso para los gráficos 4-regulares pero Dror Weitz dio un PTAS para contar conjuntos independientes de gráficos -Regular para cualquier [3]. (En el modelo sobre el que escribe, contar conjuntos independientes corresponde a tomar )$d$$d\leq5$$\lambda=1$

Cálculo de la permanente de una matriz 0-1 también es #P -Hard (esto es en el original de Valiant #P de papel [2]), pero, relajante su requisito un poco, hay una FPRAS debido a Jerrum y Sinclair [1]. Esto corresponde a contar coincidencias perfectas en gráficos bipartitos.

Referencias

[1] Mark Jerrum y Alistair Sinclair, "Aproximándose a lo permanente". SIAM Journal on Computing , 18 (6): 1149–1178, 1989. ( PDF )

[2] Leslie Valiant, "La complejidad de calcular lo permanente". Informática teórica , 8: 189-201, 1979. ( PDF )

[3] Dror Weitz, "Contando conjuntos independientes hasta el umbral del árbol". STOC 2006. (Versión completa no publicada: PDF .)

Añadiendo otro ejemplo que encontré, con un resultado aún más fuerte:

Existe un FPTAS (determinista) para el problema de contar el número de coincidencias en un gráfico bipartito de grado acotado, mientras que este es un problema completo de .$\#P$