Apakah #

Biarkan menjadi beberapa masalah penghitungan yang dikenal sebagai # P -Lengkap .$\Pi$$P$

Apakah itu menyiratkan bahwa adalah A P X -hard (yaitu tidak ada PTAS untuk masalah ada kecuali P = N P )?$\Pi$$APX$$P=NP$

Tidak. Menghitung set independen dalam grafik adalah # P -hard , bahkan untuk grafik 4-reguler tetapi Dror Weitz memberikan PTAS untuk menghitung set independen grafik reguler untuk setiap d ≤ 5 [3]. (Dalam model yang ia tulis, menghitung set independen sesuai dengan mengambil λ = 1. )$d$$d\leq5$$\lambda=1$

Komputasi permanen dari matriks 0-1 juga #P -hard (ini ada dalam kertas #P asli Valiant [2]) tetapi, sedikit mengurangi kebutuhan Anda, ada FPRAS karena Jerrum dan Sinclair [1]. Ini sesuai dengan penghitungan kecocokan sempurna dalam grafik bipartit.

Referensi

[1] Mark Jerrum dan Alistair Sinclair, "Mendekati yang permanen." Jurnal SIAM tentang Komputer , 18 (6): 1149–1178, 1989. ( PDF )

[2] Leslie Valiant, "Kompleksitas komputasi yang permanen." Ilmu Komputer Teoritis , 8: 189–201, 1979. ( PDF )

[3] Dror Weitz, "Menghitung set independen hingga ambang batas pohon." STOC 2006. (Versi lengkap tidak dipublikasikan: PDF .)

Menambahkan contoh lain yang saya temui, dengan hasil yang lebih kuat:

$\#P$