Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Wednesday, December 14, 2005
Physicists and Complexity
In my second Complexitycast, Scott
Aaronson and I try to answer the question "What should physicists
know about computational complexity?" MP3
(21:52, 3.8MB)
How come Scott says that the soap bubbles form a steiner tree and not just a tree, because how do you highlight the steiner nodes? You just give the soap bubbles pegs on the glass, so if it finds a tree connecting all the pegs, then it is not a steiner tree, just a tree and possibly an MST.
Relating to Scott's comment about physical limits, and the (im)possibility of solving efficiently NP-complete problmes with some physical model of computation.
How about DNA computing? Few years ago I took biological and molecular computing graduate course in my U. In that class professor explained that somebody had deviced an experiment where hamiltonian circuit was solved by DNA reactions (I don't remember the details anymore though). Of course he did not describe any general model of computation with DNA molecules, but just one-shot experiment.
So my question is: Could "massive parallelism" of DNA molecular reactions be used to create universal turing machine like computational model, with more power than quantum computer?
As a side note, during the course we visited the biology wetlab and for a computer scientist that was kinda cool, our labs are only filled with normal PC's. Biologists have real labs. :-)
DNA computing is "the same" as standard computing, other than the fact that due to sheer numbers you get massive parallelism. (You could achieve the same result as DNA computing if you could throw 10^{23} standard computers at the problem.) The point is that the parallelism in DNA computing is NOT like the "parallelism" in quantum computing.
Perhaps you should have a feature on "What complexity theorists should know about Physics", too, just for symmetry (invite a Physicsist over, like David Bacon, for instance). Also interesting will be to let complexity theorists know where to learn this physics material from, i.e., in a form that is accessible to computer scientists.
So my question is: Could "massive parallelism" of DNA molecular reactions be used to create universal turing machine like computational model, with more power than quantum computer?
At best DNA computing can produce a constant factor speed-up whereas quantum computing does much more than this in certain instances. Some of the interest in DNA computing has stemmed from the fact the constant theoretically depends on Avogadro's number which is quite large. It is not clear that it scales in practice, however.
The interest in DNA computing these days seems to be more in the area of self-assembly than in fast computation.
Via a quick jaunt to the Zoo, I can point out that if quantum computing can solve NP-complete probs fast then it can tackle the whole Polynomial Hierarchy--circuit minimization, bounded-depth games, etc. This because BQP^BQP = BQP.
Still haven't been convinced one way or the other about its power. Tell me why I shouldn't believe it's either P or PSPACE.
Anonymous: No, we don't know how to show that if NP is in BQP then PH is in BQP as well. Try it: suppose NP is in BQP. Then NP^NP is in NP^BQP is in ... oops! Our assumption wasn't strong enough to conclude that NP^BQP is in BQP^BQP = BQP. For that we'd need something stronger, like BQP=QCMA.
A reason to believe BQP!=P is that factoring is in BQP. A reason to believe BQP!=PSPACE is that relative to an oracle, BQP doesn't even contain NP.
Of course, until these conjectures are proven, you're welcome to believe anything you like about them. I'm just talking about what's true. :)
Sure. BQP is in PP, so if it equalled PSPACE we'd have PP=PSPACE, which would be a big collapse. :-)
But the real question is why we should take oracle separations seriously, if they got IP vs. PSPACE so dramatically wrong. I try to answer that question in Section 5.2 of my thesis:
Would PP = PSPACE really be such a big collapse? I wonder how man complexity theorists can honestly aver a strong belief in the separation of those classes.
I had a look at Section 5.2 in your thesis. The first reason you give is the only one relevant to the question at hand. As for oracle results and the "beginnings of understanding", this does sound very credible in principle. However, of the existing results in complexity theory that did not relativize, I cannot think of a single example where the oracle had any connection with the ultimate solution. And yes, black-box results may be interesting technically, but that's orthogonal to the question of philosophical value.
As for quantum oracles being more significant than classical ones, it's a possibility but again there's no a priori reason to believe it. In general, I think it's very misleading to cite an oracle result as saying something about the probability of a theorem being true or our belief in a theorem. We all know what happened to the random oracle hypothesis...
So much for belief, and reasons for belief. Turning to more ojective matters, do you believe there is some stronger reason for believing BQP != PSPACE, such as PH collapsing :)?
Cheshire Cat: What sort of evidence would make you happy (short of an unconditional separation)? If you're not impressed by oracle separations, then why be impressed by collapses of PH? Who knows, maybe PH does collapse! :)
As for your specific question: since we don't know if BQP is in PH, I don't know how to show that if BQP=PSPACE then PH collapses. Various other hierarchies would collapse, like the counting hierarchy (PP, PP^PP, etc.) and the QMA hierarchy (QMA, QMA^QMA, etc.).
But (joking aside) nobody takes that as "evidence" that BQP!=PSPACE. If you smashed together BQP and PSPACE, then obviously you'd smash together everything between them too!
Ultimately, it all comes down to the belief that the linearity of quantum mechanics imposes a fundamental constraint on efficient quantum computation, preventing one branch of the wavefunction from "shouting above the rest." When we try to express that belief to the unconverted, we fall back on results like oracle lower bounds or limitations of the adiabatic algorithm -- but a skeptic could always scoff that we haven't so much justified the belief as clarified what we mean by it.
In which case, the best I can do is turn the tables on the skeptic. Don't draw me a black box containing a quantum algorithm for PSPACE, and remind me that no one has proven its nonexistence. Open the box just a crack. Tell me something about it. Paint me a picture of what the world would be like if it existed.
So if you ever wondered why the behavior of complex mechatronic systems (that include multiple feedback loops) can't be predicted with certainty, this is why! And of course, the same applies to system biology ... which to an engineer is just dynamical control theory writ small.
So when von Neumann famously predicted "All stable processes we shall predict. All unstable processes we shall control.", he overlooked a third possibility that his generation of scientists and engineers did not envision. Namely, that generic complex systems are resistant to both reductionist prediction and reliable stabilizing control.
Which accords pretty well with common sense and common experience, when you reflect on it.
Oh yeah, an even more surprising result is that some reasonably natural questions in control engineering are in the class "undecidable".
It is certainly not clear to me that a quantum computer could ever make headway in solving problems in this complexity class (assuming, "undecidable" is even a complexity class).
How come Scott says that the soap bubbles form a steiner tree and not just a tree, because how do you highlight the steiner nodes? You just give the soap bubbles pegs on the glass, so if it finds a tree connecting all the pegs, then it is not a steiner tree, just a tree and possibly an MST.
ReplyDeleteRelating to Scott's comment about physical limits, and the (im)possibility of solving efficiently NP-complete problmes with some physical model of computation.
ReplyDeleteHow about DNA computing? Few years ago I took biological and molecular computing graduate course in my U. In that class professor explained that somebody had deviced an experiment where hamiltonian circuit was solved by DNA reactions (I don't remember the details anymore though). Of course he did not describe any general model of computation with DNA molecules, but just one-shot experiment.
So my question is: Could "massive parallelism" of DNA molecular reactions be used to create universal turing machine like computational model, with more power than quantum computer?
As a side note, during the course we visited the biology wetlab and for a computer scientist that was kinda cool, our labs are only filled with normal PC's. Biologists have real labs. :-)
DNA computing is "the same" as standard computing, other than the fact that due to sheer numbers you get massive parallelism. (You could achieve the same result as DNA computing if you could throw 10^{23} standard computers at the problem.) The point is that the parallelism in DNA computing is NOT like the "parallelism" in quantum computing.
ReplyDeletePerhaps you should have a feature on "What complexity theorists should know about Physics", too, just for symmetry (invite a Physicsist over, like David Bacon, for instance). Also interesting will be to let complexity theorists know where to learn this physics material from, i.e., in a form that is accessible to computer scientists.
ReplyDeleteI totally had the apparently common misconception that quantum computing would solve\ NP-complete problems in polynomial time. Now I'm heartbroken!
ReplyDeleteSo my question is: Could "massive parallelism" of DNA molecular reactions be used to create universal turing machine like computational model, with more power than quantum computer?
ReplyDeleteAt best DNA computing can produce a constant factor speed-up whereas quantum computing does much more than this in certain instances. Some of the interest in DNA computing has stemmed from the fact the constant theoretically depends on Avogadro's number which is quite large. It is not clear that it scales in practice, however.
The interest in DNA computing these days seems to be more in the area of self-assembly than in fast computation.
"I totally had the apparently common misconception that quantum computing would solve NP-complete problems in polynomial time. Now I'm heartbroken!"
ReplyDeleteAnd my heart is warmed. Thank you for making my day.
Via a quick jaunt to the Zoo, I can point out that if quantum computing can solve NP-complete probs fast then it can tackle the whole Polynomial Hierarchy--circuit minimization, bounded-depth games, etc. This because BQP^BQP = BQP.
ReplyDeleteStill haven't been convinced one way or the other about its power. Tell me why I shouldn't believe it's either P or PSPACE.
Anonymous: No, we don't know how to show that if NP is in BQP then PH is in BQP as well. Try it: suppose NP is in BQP. Then NP^NP is in NP^BQP is in ... oops! Our assumption wasn't strong enough to conclude that NP^BQP is in BQP^BQP = BQP. For that we'd need something stronger, like BQP=QCMA.
ReplyDeleteA reason to believe BQP!=P is that factoring is in BQP. A reason to believe BQP!=PSPACE is that relative to an oracle, BQP doesn't even contain NP.
Of course, until these conjectures are proven, you're welcome to believe anything you like about them. I'm just talking about what's true. :)
woops, Scott's right of course.
ReplyDelete"A reason to believe BQP != PSPACE is that relative to an oracle, BQP doesn't even contain NP".
ReplyDeleteA reason to believe IP != PSPACE is that relative to an oracle, IP doesn't even contain coNP.
Are there other "reasons" to believe...?!
"Are there other 'reasons' to believe...?!"
ReplyDeleteSure. BQP is in PP, so if it equalled PSPACE we'd have PP=PSPACE, which would be a big collapse. :-)
But the real question is why we should take oracle separations seriously, if they got IP vs. PSPACE so dramatically wrong. I try to answer that question in Section 5.2 of my thesis:
http://www.scottaaronson.com/thesis.html
Would PP = PSPACE really be such a big collapse? I wonder how man complexity theorists can honestly aver a strong belief in the separation of those classes.
ReplyDeleteI had a look at Section 5.2 in your thesis. The first reason you give is the only one relevant to the question at hand. As for oracle results and the "beginnings of understanding", this does sound very credible in principle. However, of the existing results in complexity theory that did not relativize, I cannot think of a single example where the oracle had any connection with the ultimate solution. And yes, black-box results may be interesting technically, but that's orthogonal to the question of philosophical value.
As for quantum oracles being more significant than classical ones, it's a possibility but again there's no a priori reason to believe it. In general, I think it's very misleading to cite an oracle result as saying something about the probability of a theorem being true or our belief in a theorem. We all know what happened to the random oracle hypothesis...
So much for belief, and reasons for belief. Turning to more ojective matters, do you believe there is some stronger reason for believing BQP != PSPACE, such as PH collapsing :)?
Cheshire Cat: What sort of evidence would make you happy (short of an unconditional separation)? If you're not impressed by oracle separations, then why be impressed by collapses of PH? Who knows, maybe PH does collapse! :)
ReplyDeleteAs for your specific question: since we don't know if BQP is in PH, I don't know how to show that if BQP=PSPACE then PH collapses. Various other hierarchies would collapse, like the counting hierarchy (PP, PP^PP, etc.) and the QMA hierarchy (QMA, QMA^QMA, etc.).
But (joking aside) nobody takes that as "evidence" that BQP!=PSPACE. If you smashed together BQP and PSPACE, then obviously you'd smash together everything between them too!
Ultimately, it all comes down to the belief that the linearity of quantum mechanics imposes a fundamental constraint on efficient quantum computation, preventing one branch of the wavefunction from "shouting above the rest." When we try to express that belief to the unconverted, we fall back on results like oracle lower bounds or limitations of the adiabatic algorithm -- but a skeptic could always scoff that we haven't so much justified the belief as clarified what we mean by it.
In which case, the best I can do is turn the tables on the skeptic. Don't draw me a black box containing a quantum algorithm for PSPACE, and remind me that no one has proven its nonexistence. Open the box just a crack. Tell me something about it. Paint me a picture of what the world would be like if it existed.
Both physicists and mathematicians would do well to keep in mind---something which engineers know full well---that a great many (even most) practical problems in control theory are now known to be in complexity class NP-hard.
ReplyDeleteSo if you ever wondered why the behavior of complex mechatronic systems (that include multiple feedback loops) can't be predicted with certainty, this is why! And of course, the same applies to system biology ... which to an engineer is just dynamical control theory writ small.
So when von Neumann famously predicted "All stable processes we shall predict. All unstable processes we shall control.", he overlooked a third possibility that his generation of scientists and engineers did not envision. Namely, that generic complex systems are resistant to both reductionist prediction and reliable stabilizing control.
Which accords pretty well with common sense and common experience, when you reflect on it.
Oh yeah, an even more surprising result is that some reasonably natural questions in control engineering are in the class "undecidable".
ReplyDeleteIt is certainly not clear to me that a quantum computer could ever make headway in solving problems in this complexity class (assuming, "undecidable" is even a complexity class).