Thursday, November 13, 2014

From Homework Solution to Research Paper

Inspired by the Dantzig Story  I occasionally put an open problem on a class assignment. Never worked, though I did have a student get a research paper from solving a homework question the hard way.

Teaching in the early 90's, I showed Valiant's proof that computing the permanent of a 0-1 matrix was #P-complete, including showing that the 0-1 permanent was in #P, the class of functions representable as the number of accepting paths of a nondeterministic polynomial-time Turing machine.

I gave a homework assignment to show that the permanent of a matrix with non-negative integer entries was in #P. The answer I expected was to construct an appropriate NP machine whose number of accepting paths equalled the permanent and some students came up with such a proof.

One of the students Viktória Zankó took a different approach, creating a reduction that mapped an integer matrix A to a 0-1 matrix B such that permanent(A) = permanent(B). A fine solution reducing the problem to a previously solved case.

So what's the rub? Such a reduction was an open problem and simplified Valiant's paper. Valiant only had the reduction for integer matrices A with small entries and needed a mod trick to show the 0-1 permanent is #P-complete. Zankó's construction eliminated the need for the mod trick.

And that's how Viktória Zankó got a research paper from solving a homework problem.

5 comments:

  1. I knew this paper but not the story behind it, thanks!

    ReplyDelete
  2. This blog post is essentially a duplicate of a previous post, see: http://oldblog.computationalcomplexity.org/archive/2003_03_01_archive.html , in particular the entry from March 14, 2003.

    ReplyDelete
    Replies
    1. You have a better memory than I do. I did a search for Zanko before I wrote today's post but "Zanko" didn't match "Zankó". Sorry for the duplicate and hopefully those who are newer to my blog find this post interesting.

      Delete
  3. Neither my university nor the Max Planck Society have access to this article, so I just spent 20 British pounds of taxpayer money to learn that the trick is: Replace every "-1" in the -1/0/1-Permanent with a gadget of weight 3^n * n!.

    ReplyDelete
  4. Hi Lance! It is easy to transform a finite set A of integers into a Turing machine which decides these elements when they belong to A. Suppose we already have this Turing Machine M for some set A. Then, checking if some element x is the minimum in A would be equivalent to check if x is the minimum element which accepts M. I found this circunstance fascinating, because in the second case we could prove that x is the minimum in less than |A| steps. We already know that |A| - 1 is the lower bound to find the minimum of an integer set. However, when we change to this other model the order could change in relation to the size of x and not of A. I guess this might not be possible, because the size of A could be exponential in relation to the bit-length of x. Besides, I suspect we could not polynomially relate the enconding of some M and x (inside of an interval) to A and x . I found this has a close relation to the P versus NP problem and I shared as a preprint.

    https://hal.archives-ouvertes.fr/hal-01087331

    I presented as a conjecture and shared my opinion about it. I want to share it to you. Maybe it could be interesting and not some naive issue.

    ReplyDelete