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