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

#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 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 Dave Bacon December 14, 2008
Dudes, no. Race!

#4 Joe Fitzsimons December 14, 2008
Well the fact that the abstract seems to be selling graph isomorphism as NPhard doesn’t inspire confidence.

#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 NPhard.
So going solely from the abstract, an obvious undergradlevel FAIL would be finding a fast solution to bipartite perfect matching and trying to generalize from that. 
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 #Pcomplete [Val79] even though the search problem has long been known to be in P [Edm65].

#7 Aaron December 15, 2008
I have a filter for arXiv papers: I refuse to read ones which are PDF only.

for NE1: If I discovered an algorithm for efficiently solving NPhard 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, Wilesstyle, 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 matt December 15, 2008
Other than the geometric complexity program, do any computer scientists actually spend time trying to prove P \neq NP?

#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 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”

#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 nontraditional career path.

#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 `runon sentence?’ Man, I’m tired…

#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 K_{n,n}. That’s all well and good, but that counting is O(n^{2}) [that's a WAG] specifically because the graph is symmetric. He really needs to prove something about counting the perfect matchings on K_{m,n}, m != n, to collapse the polynomial hierarchy.
And by the by, there are no Hamiltonian cycles on K_{m,n}, when m – n > 1 [which means you could be looking forever for a perfect matching].

#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 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 reread it in enough detail to confirm that hunch.
Reference: http://people.seas.harvard.edu/~valiant/
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.

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 firsthand 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.

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 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 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 …