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.
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 :)?
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.
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.
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...?!
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 :)?
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).