Czy #

Niech będzie jakimś problemem liczenia, o którym wiadomo, że to # -Complete .$\Pi$$P$

Czy to oznacza, że jest -hard (czyli nie PTA dla istnieje problem chyba że )?$\Pi$$APX$$P=NP$

Nie. Liczenie niezależnych zestawów na wykresie to # P-twarde , nawet dla wykresów 4-regularnych, ale Dror Weitz podał PTAS do zliczania niezależnych zestawów wykresów regularnych dla dowolnego d ≤ 5 [3]. (W modelu, o którym pisze, liczenie niezależnych zbiorów odpowiada przyjęciu λ = 1 ).$d$$d\leq5$$\lambda=1$

Obliczenie stałej macierzy 0-1 jest również # P-twarde (jest to w oryginalnym artykule #P Valianta [2]), ale nieco rozluźniając twoje wymagania, istnieje FPRAS z powodu Jerruma i Sinclaira [1]. Odpowiada to liczeniu idealnych dopasowań na wykresach dwustronnych.

Bibliografia

[1] Mark Jerrum i Alistair Sinclair, „Przybliżenie permanentu”. SIAM Journal on Computing , 18 (6): 1149–1178, 1989. ( PDF )

[2] Leslie Valiant, „Złożoność obliczania stałego”. Theoretical Computer Science , 8: 189–201, 1979. ( PDF )

[3] Dror Weitz, „Liczenie niezależnych zestawów do progu drzewa”. STOC 2006. (Niepublikowana pełna wersja: PDF .)

Dodając kolejny przykład, z którym się spotkałem, z jeszcze silniejszym rezultatem:

Istnieje (deterministyczny) FPTAS dla problemu zliczania liczby dopasowań na dwustronnym grafie z ograniczonym stopniem, podczas gdy jest to problem uzupełniający $\#P$