Going back to the problem we skipped over last week.

**The problem: **Permanent Evaluation. This is problem AN13 in the appendix.

**The description: **Given an nxn matrix M of 0’s and 1’s, and a positive integer K, is the permanent of M equal to K?

**Example: **The permanent of M =

That is, for each permutation of the columns, we multiply down the main diagonal. The sum of all of those products is the permanent.

1 | 2 | 3 |

4 | 5 | 6 |

7 | 8 | 9 |

..then the permanent is 1*5*9 + 1*6*8 + 2*4*9 + 2*6*7 + 3*5*7 + 3*4*8 = 450

Of course, we’re looking at 0/1 matrices, so I think what we’re really asking is how many permutations of the columns have 1’s on the main diagonal.

**Reduction: **If I’m right above that all we’re doing is counting how many ways there are 1’s in the main diagonal, then this becomes a pretty easy Turing Reduction from Hamiltonian Path. Given an adjacency matrix of a graph, we want to know if the permanent of the adjacency matrix is 1 or more. (Any Hamiltonian Path will give a permutation that multiplies to 1, and any permutation of vertices that is not a Hamiltonian Path multiplies to 0). Given how complicated the “actual” reduction is, I’m a little worried that I missed something, though.

The reduction by Valiant that G&J point you to uses 3SAT, He shows that if you have a formula F, and define t(F) to be 2x the number of literals in F – the number of clauses in F, then there is some function f, computable by a deterministic Turing Machine in polynomial time, that maps a formula to a matrix. (The matrix has entries in {-1..3}, he does another transformation later to convert it to a 0/1 matrix). The permanent of that matrix = , where is the number of ways to satisfy F.

Since one of the consequences of Cook’s Theorem is that we can take an arbitrary non-deterministic Turing Machine and turn it into a Satisfiability formula, we get the reduction.

The actual construction of that function f is complicated. Given a formula, we construct a graph and use the matrix as the adjacency matrix of the graph. The variables, literals, and clauses get mapped to subgraphs.

**Difficulty: **If my way is right, I’d give it a 4- I think it’s easier than most Turing Reductions. The Valiant construction is an 8.