The latest P=NP saga on comp.theory involved soap bubbles: the first post in the thread:
The paper is the best argument I have heard for P=NP, even though I believe the opposite. It can be found here: http://arxiv.org/abs/cs.CC/0406056. It brings out a great question.
Basically, the argument is that since soap bubbles can be made to solve NP-complete problems, particularly the Steiner tree graph problem, in what appears to be polynomial time and physics on a macroscopic level can be modeled as a Turing machine, it must be true that P=NP.
What I would like to know from any physicists out there is why do soap bubbles work in such a way that they are able to solve the Steiner tree graph problem?How is nature able to quickly solve problems that we cannot solve quickly?
Scott Aaronson, in
a post downstream:
Motivated by this newsgroup discussion, this week I did the experiment. At a hardware store I bought two 8"x9" glass plates; paint to mark grid points on the plates; thin copper rods which I cut into 1" pieces; suction cups to attach the rods to the plates; Murphy liquid oil soap; and a plastic tub to hold the soapy water. I also bought work gloves, since at one point I cut my hand handling the glass.
The post
continues: read it all. He even has a
picture.
Since planar steiner tree is probably easy in practice (like planar TSP which in practice can be solved for thousands of points), it might be safe to assume this is not relelvant. Indeed, to beat existing computer programs you need to run instances with hundreds of thousands of points in the plane. At this point the physical noise is going to be so dominant, that whatever you are going to get from it is going to be noise.
ReplyDeleteNot to mention that the physical solution is only approximate and converges to a local minimum, not a golbal one. In short, dont throw away your new super computer, it might still be useful for something.
For each finite size Hard NP problem there is a finite network of entangled Bose-Einstein condensates that can cycle through all the permutations in absolutely no time.
ReplyDelete