"Holographic Algorithms" method threatens collapse of complexity classes (P could = NP!)

http://pages.cs.wisc.edu/~jyc/papers/HA-survey.pdf

by injesus • 19 years ago

12 10 19 years ago

pages.cs.wisc.edu

Very Interesting!

tlrobinson3• 19 years ago

For those who don't want to read the whole thing, here's the part I found most interesting (though I didn't get through it all either...):

In this article, we will survey the new algorithm design method called holographic algorithms. This method uses perfect matching as a basic coding technique to encode computations, and then the FKT-algorithm to carry out the final computation. A particularly innovative idea is to choose a set of linear basis vectors to express and interpret a desired computation. In effect the algorithm is designed to manipulate sums of perfect matchings in superpositions, while the speed up is achieved by cancellations among such "holographic mixes". These holographic algorithms are quite unlike anything before, except perhaps quantum algorithms. At the heart of the computation is a process of introducing and then canceling exponentially many computational fragments. But unlike quantum algorithms, these holographic algorithms produce classical polynomial time algorithms. So far this method has produced some exotic algorithms for problems which were not known to be in P previously, and minor variations of which are known to be NP-complete or NP-hard.

The most intriguing question is whether this new theory can lead to any collapse of complexity classes. We contend that our belief of NP != P is based on the sense and experience that the usual algorithmic paradigms are insufficient for NP-hard problems (we don't have strong lower bounds for general models of computation). But does our erstwhile experience apply to these new exotic algorithms? If the answer is no, then it is conceivable that the new methodology may lead to a radically revised conception of P vs. NP. Of course it is quite possible that the theory of holographic algorithms does not in the end lead to any collapse of complexity classes. But even in this eventuality, as Valiant suggested in [54], "any proof of P != NP may need to explain, and not only to imply, the unsolvability" of NP-hard problems using this approach.

mxh• 19 years ago

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.

amichail3• 19 years ago

Welcome to theoretical computer science.

greendestiny2• 19 years ago

Take this with a grain of salt, because I'll admit I didn't read it very thoroughly. My understanding of holographic algorithms is that they make a primitive out of a matching algorithms that could be executed in constant physical time with holographic storage. While thats great, I think it only fair to include the complexity of the matching in the overall algorithms complexity, because although it happens in constant time this only because of massively parallel interactions in the storage.

Still I think when the author says that P != NP proofs will have to address this I think he's right that that is important. It means that this is at the crux of the issue, either way it goes.

amichail3• 19 years ago

My understanding of holographic algorithms is that they make a primitive out of a matching algorithms that could be executed in constant physical time with holographic storage.

Actually, from what I understand, that's not the point at all! What is "holographic storage" btw?

greendestiny2• 19 years ago

http://en.wikipedia.org/wiki/Holographic_data_storage

The whole point being that the reference signal can be projected into the storage and match found in a single pulse. Holographic algorithms deal generally with algorithms based on interference, so they might not directly relate to a physical storage device but the principles are similar.

"Holographic Algorithms" method threatens collapse of complexity classes (P could = NP!)

Related Stories