For example, the Steiner Tree problem (STP) is
known to be NP-complete ... Nonetheless, a simple
physical process (termed an analog computation)
can apparently solve it quickly.
No, it can't. Small, trivial cases can be solved, but I believe it's been shown that when you get to mildly interesting cases it's just as likely to find non-optimal solutions, and sometimes even more likely to find non-optimal solutions.
This is at the top of page 2, and it doesn't bode at all well. Section 3 of Aaronson's paper[0] discusses this explicitly, and comes to the conclusion that, not to put too fine a point on it, it doesn't work.
I see that sort of thing a lot, where a simple model appears to violate some algorithmic boundary, but a more complete analysis reveals that all is well.
For example, take "spaghetti sort." This is a weird physical sorting algorithm where you represent each number to be sorted as a physical strand of uncooked spaghetti of corresponding length. To perform the sort, you grab the spaghetti in a bundle and place it on a table so the bottom of each spaghetti strand is on the table. Then you put your other hand on top, find the longest strand, and pull it out. Repeat this process once for each strand, and you then have all the numbers in order.
This is described as a "linear time" algorithm because you perform the same procedure once per number, so it's clearly O(n). It's obviously impractical for real-world use, but if you had some utterly ridiculous quantity of numbers, maybe it could be the best way!
But of course this ignores important factors. For example, the radius of the bundle will increase with the square root of the number of strands present within it. Whatever you use to select and retrieve the longest strand must move at some finite speed to traverse this distance, which means that the actual running time is O(n^1.5), substantially worse than the theoretical O(n log n) limit!
Another factor that is often ignored is the fact that analog systems don't actually have infinite precision. If you look at their actual (or even theoretical) precision and convert that to bits, it's not all that many! Lots of analog solutions can look extremely clever and quick, until you realize that it's just solving the problem for a 28-bit number, or whatever.
I consider those the Brownian ratchets [1] of computing. Interesting to model and see what's going on!
Here's another variation: arrange the sticks in a line. Have a pole scan the sticks from the top, and when the pole is impeded, record it's height. You've just computed max(a1,...,aN) in O(1) time?! (disproving is left as an exercise -- note you can even assume the pole is weightless and infinite!)
Relativity tells us that disturbances in the pole cannot move faster than the speed of light. Therefore the time it takes to find out that your pole hit something is O(n), since the location of the tallest element will be on average halfway down your line.
Of course, there's the much more obvious problem that "arrange the sticks in a line" requires manipulating each stick, and is thus O(n)!
Correct, of course :) Maybe it's not that good example... I was trying to come up with a way to obfuscate the speed of light limitation (one usually thinks of poles as rigid). A thing I like about those is even if they're really simple they highlight limits like the Bekenstein bound: you can make your experiment arbitrarily large, but if you allow it to shrink arbitrarily (as a function of n), you get unexpected results (essentially BSS machines[1] versus Turing machines?) -- in your example you could actually sort the numbers in O(n).
Aaronson put quite a fine point on it! "In
short, then, I found no reason to doubt the 'party line,' that soap bubbles do not solve NP-complete
problems in polynomial time by magic."
The paper is a good read, by the way. Everyone here should skip the posted article, and read Aaronson's.
If detecting the suboptimal answer takes better than exponential time, and blowing takes linear time, the total time is still better then exponential and doesn't disprove the argument. It depends how many times you have to repeat this to guarantee a optimal solution.
But I agree that the argument is badly flawed(1). The soap bubble STP machine and and similar machines are probabilistic solvers. They are doing stochastic gradient descent from initial conditions, with the usual lack of global optimal convergence guarantee.
(1) It may be satire. Does anyone know if this is so?
The video isn't supposed to be a proof that no technique can do it; the video just demonstrates that soap bubbles can get stuck in a local minimum.
(Also, blowing is not guaranteed to move the answer towards the global solution. Even if you can quickly determine that an answer is not optimal and blow it around, you could just spend forever going in circles.)
I agree with you. Many of the NP-complete problems are appealing because they don't seem difficult to solve at first glance. The fact that there are simple physical processes that do a good job for small cases doesn't surprise me, one can solve many of these problems by hand for small values of n. But, O(e^n) makes the big cases intractable even if the small cases are very very easy. It is the behavior of the algorithms as n gets large that is important and demonstrations of physical analog methods to solve modest cases doesn't seem relevant for the reasons that you mention.
I think it is rooted in a common fallacy -- inability to intuitively understand exponential behaviour. In can be something common such as compounding interest on a loan or something like this related to computational problems.
Specifically, I was under the impression the soap-based solution to the STP problem was prone to hitting local minima, as it's effectively a gradient descent from a random starting point.
This is at the top of page 2, and it doesn't bode at all well. Section 3 of Aaronson's paper[0] discusses this explicitly, and comes to the conclusion that, not to put too fine a point on it, it doesn't work.
In essence, looks like complete nonsense to me.
[0] http://arxiv.org/pdf/quant-ph/0502072v2.pdf