Soit un problème de comptage connu pour être # -Complete .P
Cela implique-t-il que est -hard (c'est-à-dire qu'il n'y a pas de PTAS pour le problème sauf si )?A P X P = N P
11
Non Counting ensembles indépendants dans le graphique est #P -Hard, même pour les graphes 4 réguliers , mais Dror Weitz a donné un PTAS pour compter ensembles indépendants de graphiques pour tout réguliers réguliers [3]. (Dans le modèle sur lequel il écrit, compter les ensembles indépendants correspond à prendre )d ≤ 5 λ = 1
Le calcul du permanent d'une matrice 0-1 est également #P -hard (c'est dans le papier #P original de Valiant [2]) mais, en relâchant un peu votre besoin, il y a un FPRAS dû à Jerrum et Sinclair [1]. Cela correspond au comptage des correspondances parfaites dans les graphiques bipartites.
Les références
[1] Mark Jerrum et Alistair Sinclair, "Approximation du permanent". SIAM Journal on Computing , 18 (6): 1149–1178, 1989. ( PDF )
[2] Leslie Valiant, "La complexité du calcul du permanent." Informatique théorique , 8: 189–201, 1979. ( PDF )
[3] Dror Weitz, "Compter les ensembles indépendants jusqu'au seuil d'arbre." STOC 2006. (Version complète non publiée: PDF .)
En ajoutant un autre exemple, je suis tombé sur un résultat encore plus fort:
Il existe un FPTAS (déterministe) pour le problème du comptage du nombre de correspondances dans un graphe biparti à degrés bornés, alors qu'il s'agit d'un problème -complet.