Изменения
→Примеры #P-полных задач
*Посчитать количество возможных подстановок, для которых заданная в ДНФ формула будет удовлетворена.
*Посчитать количество полных паросочетаний в данном двудольном графе.
*<tex>perm</tex>Вычислить значение перманента матрицы, заполненной нулями и единицами.
*Посчитать количество способов раскрасить заданный граф в <tex>k</tex> цветов.
Тогда <tex>\prod\limits^n_{i =1}A_{i\sigma(i)} = 1</tex> тогда и только тогда, когда <tex>\sigma</tex> является совершенным паросочетанием. В таком случае, <tex>perm(A)</tex> равен числу совершенных паросочетаний в графе <tex>G</tex>.
Нам известно, что задача <tex>\#SAT</tex> является <tex>\#P</tex>-полной. Аналогично задачам <tex>SAT</tex> и <tex>3SAT</tex> мы можем сказать, что задача <tex>\#SAT</tex>может быть сведена к задаче <tex>\#3SAT</tex>, которая также будет <tex>\#P</tex>-полной. Сведем задачу <tex>\#3SAT</tex> к задаче <tex>perm</tex>. По данной формуле <tex>\phi</tex> с <tex>n</tex> переменными и <tex>m</tex> "клозами" построим целочисленную матрицу <tex>A'</tex> такую, что <tex>perm(A')=4^m\cdot(\#\phi)</tex>, где <tex>\#\phi -</tex> количество удовлетворяющих постановок для <tex>\phi</tex>.
}}
