News for hackers. Stuff that matters.
Re:"Holographic Algorithms" method threatens collapse of com... by mxh on Friday December 07, 2007 @03:08AM (#86935)
Two things leap out at me:

"So far this method has produced some exotic algorithms for ... minor variations of [problems] which are known to be NP-complete or NP-hard."

Well, I guess all they have to show is that those "minor" variations don't take the problems out of NP-complete or NP-hard .... that should be pretty easy, right?

"'any proof of P != NP may need to explain, and not only to imply, the unsolvability' of NP-hard problems using this approach."

Uhm - so, when and if someone gets around to the Turing-award winning business of proving P != NP, that proof may need to specifically address this technique? And that makes the technique important?

At first blush, I think there's a snake around here somewhere that's a quart low. The authors might be on to something, but they look bad in this extract. They might have found something ("exotic algorithms for problems which were not known to be in P previously") interesting, but P == NP seems like overselling it, and that casts doubt on the value of the whole enterprise.

Re:"Holographic Algorithms" method threatens collapse of com... by amichail on Friday December 07, 2007 @09:34AM (#86996)
Welcome to theoretical computer science.
Re:"Holographic Algorithms" method threatens collapse of com... by tlrobinson on Friday December 07, 2007 @10:59AM (#87024)
Q: How many theoretical computer scientists does it take to change a light bulb?
Re:"Holographic Algorithms" method threatens collapse of com... by joshwa on Friday December 07, 2007 @11:23AM (#87033)
Re:"Holographic Algorithms" method threatens collapse of com... by tlrobinson on Friday December 07, 2007 @03:32PM (#87111)
A: No one really knows, but it's in the same complexity class as taking out the garbage.

(got that one from my algorithms course professor)