The Quantum Pontiff

A Race

Who can find what is wrong the quickest in arXiv:0812.1385 (or verify that it is correct!)? 1,2,3,….go!


  1. #1 Greg Laden
    December 14, 2008

    Hmph…. well, it is totally obvious. I worked it out in my head. I can’t believe they got that wrong!!!! LOL!!! ROFLMAO!!!!!

  2. #2 Ian Durham
    December 14, 2008

    Either this is one of those computer science things I shouldn’t necessarily be expected to know, or I am just dead tired. Are you going to eventually reveal the gaff to those of us who are complete idiots?

  3. #3 Dave Bacon
    December 14, 2008

    Dudes, no. Race!

  4. #4 Joe Fitzsimons
    December 14, 2008

    Well the fact that the abstract seems to be selling graph isomorphism as NP-hard doesn’t inspire confidence.

  5. #5 dave
    December 14, 2008

    “The first candidate problem chosen is Perfect Matching in a bipartite graph.”
    Uhh… I may be thinking of something else, but I’m pretty sure that’s not NP-hard.
    So going solely from the abstract, an obvious undergrad-level FAIL would be finding a fast solution to bipartite perfect matching and trying to generalize from that.

  6. #6 Kurt
    December 15, 2008

    for dave #5: You have to go a little farther than the abstract. The first sentence of the introduction reads:

    The counting problem for perfect matching in a bipartite graph is known to be #P-complete [Val79] even though the search problem has long been known to be in P [Edm65].

  7. #7 Aaron
    December 15, 2008

    I have a filter for arXiv papers: I refuse to read ones which are PDF only.

  8. #8 NE1
    December 15, 2008

    Why find errors when you can mock the mentally ill?

    Anyways, I’m sure this one will turn out better than the last.

  9. #9 Kurt
    December 15, 2008

    for NE1: If I discovered an algorithm for efficiently solving NP-hard problems, the first thing I’d want to do is file a patent on it! It looks like he’s been toying with this since the late 90’s. I can just imagine working in isolation, Wiles-style, all these years building up to the big announcement.

    Hey, maybe MarkCC should take a look at this paper. “Counting solutions by generating elements of a symmetric group? Even my daughter knows you can’t do that!”

  10. #10 matt
    December 15, 2008

    Other than the geometric complexity program, do any computer scientists actually spend time trying to prove P \neq NP?

  11. #11 dave
    December 15, 2008

    Kurt: “You have to go a little farther than the abstract.”
    That’s going to end up beyond what I understand pretty quickly.
    (Though it’s good to know they’re at least not making errors that are obvious to me.)

  12. #12 svat
    December 15, 2008

    Just from a glance: The word “polynomial” occurs, apart from twice in the introduction section and once in “conclusion”, exactly once in the paper. The only bound on time complexity that I could find (in 30 seconds) is in 5.1.6 which presents them as “One can easily verify the following” 🙂

  13. #13 Geordie
    December 16, 2008

    What’s the prize?
    Anyone found anything wrong with it yet?

    Kurt: You can’t patent algorithms.

  14. #14 Ian Durham
    December 16, 2008

    OK, I don’t feel so bad. Obviously the guy’s a kook but I haven’t figured out why yet but then I’m in the middle of trying to devise a super easy way to explain how to find the Jordan canonical form of a matrix to students before their final exam on Thursday so I’m already loopy.

    An interesting and somewhat serious question that this brings up is: what possesses people to toil in obscurity? My guess is that most would prefer not to. It is often difficult to find collaborators if one takes a non-traditional career path.

  15. #15 Ian Durham
    December 16, 2008

    Obviously the guy’s a kook but I haven’t figured out why yet but then I’m in the middle of trying to devise a super easy way to explain how to find the Jordan canonical form of a matrix to students before their final exam on Thursday so I’m already loopy.

    Wow. Can you say `run-on sentence?’ Man, I’m tired…

  16. #16 David
    December 16, 2008

    OK, I guess I’ll have to take a crack at it. He goes about proving that the groups of permutations are isomorphic [maybe] to the enumeration of perfect matchings on Kn,n. That’s all well and good, but that counting is O(n2) [that’s a WAG] specifically because the graph is symmetric. He really needs to prove something about counting the perfect matchings on Km,n, m != n, to collapse the polynomial hierarchy.

    And by the by, there are no Hamiltonian cycles on Km,n, when |m – n| > 1 [which means you could be looking forever for a perfect matching].

  17. #17 Warren
    December 17, 2008

    The first idea in the paper: associate a permutation of n items with a perfect matching in K_nn in the obvious way. The perfect matchings of any bipartite graph BG can be associated with a subset of the permutations on n items, denoted in the paper M(BG). So counting the number of perfect matchings in a bipartite graph is equivalent to computing the size of the set of permutations M(BG). So far, so good (and trivial).

    The paper then discusses how to find the size of M(BG) in polynomial time. There’s presumably an error somewhere, but I’ve only skimmed those sections yet so I can’t say where.

    Bottom line: I think the error is more subtle than the previous commenters suggest.

  18. #18 maybe not so wrong
    December 17, 2008

    At first blush, I think this guy may have accidentally stumbled onto one of Leslie Valiant’s “holographic algorithms”, but I haven’t had time to re-read it in enough detail to confirm that hunch.


    Even if my hunch is right, there may be errors in the paper, so caveat lector and all that.

    Disclaimers aside, if he *did* independently invent something related to holographic algorithms, it’ll be worth reading through and seeing if there’s anything novel in his paper and/or seeing if it can be fitted into Valiant’s approach; similarly, it might be the case that some of his errors may be patchable by repurposing techniques and proofs from the existing holographic algorithms literature.

  19. #19 Kurt
    December 17, 2008

    Geordie said: You can’t patent algorithms.

    Geordie, I have to defer to your knowledge in this area, since as an entrepreneur who needs to deal with IP issues you’re likely to have first-hand experience with this stuff. However, there would seem to be a gray area as far as algorithms implement in software are concerned. In the patent application linked to by NE1, Aslam cites as an example US patent 6,556,978. Reading through that, it certainly seems like a purely algorithmic invention.

  20. #20 Geordie
    December 23, 2008

    Anyone? …. Anyone? … Has he collapsed the polynomial hierarchy or not. Seems like an important thing to figure out.

    Kurt: I did some further research about this point. The case law is as you have pointed out extremely confused and there have been conflicting decisions. I am going to do a post about this on my site in the new year.

  21. #21 Joe Fitzsimons
    December 24, 2008

    Geordie, you may want to look into the RSA patent. I believe it was the patent that cleared the way for patenting algorithms and protocols. I believe the patents always refer to a computer implimentation of a specific algorithm to get around the inability to patent algorithms directly.

  22. #22 Peter Shor
    January 2, 2009

    Yes, it used to be against the rules to patent an algorithm. However, you could patent a machine which used a particular process for accomplishing some computational task, and then state (in the claims section, I believe) that your patent also covers any other machine which accomplishes the task using the same methods.

    If that’s not effectively a patent on an algorithm, I don’t know what is.

    Also, when you patented something like RSA, you had to be sure to insert claims for machines for encoding AND machines for decoding separately, because if you just patent a machine for encoding and decoding …

New comments have been disabled.