Who can find what is wrong the quickest in arXiv:0812.1385 (or verify that it is correct!)? 1,2,3,….go!
O brave new quantum world!
O brave new quantum world!
Who can find what is wrong the quickest in arXiv:0812.1385 (or verify that it is correct!)? 1,2,3,….go!
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?
Dudes, no. Race!
Hmph…. well, it is totally obvious. I worked it out in my head. I can’t believe they got that wrong!!!! LOL!!! ROFLMAO!!!!!
Well the fact that the abstract seems to be selling graph isomorphism as NP-hard doesn’t inspire confidence.
“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.
for dave #5: You have to go a little farther than the abstract. The first sentence of the introduction reads:
I have a filter for arXiv papers: I refuse to read ones which are PDF only.
Why find errors when you can mock the mentally ill?
Anyways, I’m sure this one will turn out better than the last.
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!”
Other than the geometric complexity program, do any computer scientists actually spend time trying to prove P \neq NP?
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.)
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” 🙂
What’s the prize?
Anyone found anything wrong with it yet?
Kurt: You can’t patent algorithms.
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.
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…
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].
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.
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.
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 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.
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.
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.
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 …