Изменения
→Примеры #P-Complete задач
[[Файл:xor_block.png|thumb|200px|Блок XOR]]
[[Файл:blocks_connection.png|thumb|200px|Блок XOR]]
Задача нахождения перманента <tex>0,1-</tex>матрицы принадлежит классу может быть сформулирована как задача подсчета количества перестановок, для которых произведение соответствующих элементов матрицы равно <tex>\#P1</tex>. Для вычисления В такой формулировке задача нахождения перманента недетерминированно выбирается перестановка из <tex>n0,1-</tex> элементов и для каждой такой перестановки вычисляется произведение соответствующих элементов матрицы, полученные значения складываются. Время работы такого алгоритма на недетерминированной машине Тьюринга {{---}} принадлежит классу <tex>O(n)\#P</tex>по определению.
Докажем, что задача <tex>perm</tex> является <tex>\#P-</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>.
