Computational Complexity

Friday, March 14, 2003

 
Doing homework the hard way

Posted by Lance

In yesterday's post I linked to some lecture notes of Vigoda on Valiant's result. Those notes also cite a paper of Zankó. Now every paper has a story but this one is a little more interesting than most.

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.

7:25 AM # 0 comments

Comment Feeds: This Post All