#

Пусть будет некоторой проблемой подсчета, которая известна как # P -Complete .$\Pi$$P$

Означает ли это , что является P X -Жесткий (т.е. не PTAS для проблема существует , если P = N P )?$\Pi$$APX$$P=NP$

Нет . Подсчет независимых множеств в графе является #P -трудным, даже для 4-регулярных графов , но Дрор Вайцы дали PTAS для подсчета независимых наборов -регулярных графиков для любого г ≤ 5 [3]. (В модели, о которой он пишет, подсчет независимых множеств соответствует принятию λ = 1. )$d$$d\leq5$$\lambda=1$

Вычисление перманента матрицы 0-1 также #P -Жесткий (это в оригинале искателя #P работе [2]) , но, расслабляя требование немного, есть FPRAS из - за Jerrum и Синклер [1]. Это соответствует подсчету идеальных совпадений в двудольных графах.

использованная литература

[1] Марк Джеррум и Алистер Синклер, «Приближение перманента». SIAM Journal of Computing , 18 (6): 1149–1178, 1989. ( PDF )

[2] Лесли Валиант, «Сложность вычисления перманента». Теоретическая информатика , 8: 189–201, 1979. ( PDF )

[3] Дрор Вейц, «Подсчет независимых наборов до порога дерева». STOC 2006. (Неопубликованная полная версия: PDF .)

Добавляя другой пример, я столкнулся с еще более сильным результатом:

$\#P$