A Race : The Quantum Pontiff

Search

Profile

Dave Bacon is a theoretical ski bum who is also a pseudo professor. His research is on quantum computing, his scientific passions extend to everything in physics, mathematics, computer science and beyond, and his personal pleasures include making wine, playing poker, skiing, camping, and daydreaming (although not all of those at the same time.) Nothing he says on this blog should be construed as having anything to do with his employer or his dog.

Other Information

The use of Occam's razor on this website is strickly prohibited.

Cows are well approximated by a sphere.

Subscribe to RSS feed

« Ponzi Of a Billion Dollar Kind | Main | Large Earth Collider »

A Race

Category: Computer Science
Posted on: December 14, 2008 9:11 PM, by Dave Bacon

Share:

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

Share this: Facebook Twitter Stumbleupon Reddit Email + More

TrackBacks

TrackBack URL for this entry: http://scienceblogs.com/mt/pings/87977

Comments

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

Posted by: Greg Laden | December 14, 2008 9:50 PM

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?

Posted by: Ian Durham | December 14, 2008 10:25 PM

Dudes, no. Race!

Posted by: Dave Bacon | December 14, 2008 10:55 PM

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

Posted by: Joe Fitzsimons | December 14, 2008 11:29 PM

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

Posted by: dave | December 14, 2008 11:30 PM

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

Posted by: Kurt | December 15, 2008 1:26 AM

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

Posted by: Aaron | December 15, 2008 1:36 AM

Why find errors when you can mock the mentally ill?

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

Posted by: NE1 | December 15, 2008 5:54 AM

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!"

Posted by: Kurt | December 15, 2008 9:04 AM

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

Posted by: matt | December 15, 2008 11:28 AM

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

Posted by: dave | December 15, 2008 12:23 PM

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" :-)

Posted by: svat | December 15, 2008 3:12 PM

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

Kurt: You can't patent algorithms.

Posted by: Geordie | December 16, 2008 1:43 PM

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.

Posted by: Ian Durham | December 16, 2008 3:57 PM

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

Posted by: Ian Durham | December 16, 2008 4:00 PM

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²) [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].

Posted by: David | December 16, 2008 6:50 PM

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.

Posted by: Warren | December 17, 2008 12:22 PM

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.

Posted by: maybe not so wrong | December 17, 2008 3:10 PM

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.

Posted by: Kurt | December 17, 2008 10:16 PM

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.

Posted by: Geordie | December 23, 2008 11:25 PM

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.

Posted by: Joe Fitzsimons | December 24, 2008 7:15 AM

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

Posted by: Peter Shor | January 2, 2009 10:32 PM