Permanent Evaluation

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 = \displaystyle \sum_\sigma \prod_{i=1}^n A_{i,\sigma(i)}

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.

(Wrong) 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.

Edit on 1/21: This isn’t right.  The problem is that while you’re premuting the columns, you’re not permuting the rows.  So if we permute the column to be the second vertex in the Hamiltonian Path, the second row is still the vertices adjacent to vertex #2 (which might not be the second vertex in the path).

That’s a shame.  I wonder if there is a way to manipulate the problem to make it work this way anyway.

(Correct) Reduction:

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 = 4^{t(F)} * s(F) , where s(F) 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 was right, I’d give it a 4- I think it’s easier than most Turing Reductions.  The Valiant construction is an 8.

Leave a Reply

Your email address will not be published. Required fields are marked *