In my first year as an assistant professor at the University of Chicago, I taught a graduate complexity course where I gave a homework question to show that computing the permanent of a matrix A with nonnegative integer entries is in #P. Directly constructing a nondeterministic Turing machine such that Perm(A) is the number of accepting computations of M(A) is not too difficult and that was the approach I was looking for.

In class we had shown that computing the permanent of a zero-one matrix is in #P so Viktoria Zankó decided to reduce my homework question to this problem. She came up with a rather clever reduction that converted a matrix A to a zero-one matrix B with Perm(A)=Perm(B). This reduction indeed answered my homework question while, unbeknownst to Zankó at the time, answered an open question of Valiant. Thus Zankó got a publication by solving a homework problem the hard way.

## No comments:

## Post a Comment