3 ms·

We weren’t always so lucky. One year, before we’d even finished setting up the booth, a cadre of MIT undergraduate physicists stumped us with ‘Soap bubbles ph

by QML 8y ago

We weren’t always so lucky. One year, before we’d even finished setting up the booth, a cadre of MIT undergraduate physicists stumped us with ‘Soap bubbles physically solve minimal surface problems. Are there any other physical phenomena that quickly solve NP-type problems?’ Anyone have more resources on this? I could only find a brief overview by Scott Aaronson [1]. [1]. https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf

westoncb 8y ago
The main thing I wonder about this is whether it's misleading to say the soap bubble is 'solving' a problem of high computational complexity. If we were to form a description of its state evolving, framed as a computation, then that computation would be in such and such a complexity class—sure. But if you want to go ahead and say that soap bubble is literally computing in the same sense, you're making a number of implicit philosophical commitments that I have yet to see a justification for when this subject is brought up. Edit: to clarify, what I'm getting at is whether we're using it to solve what is a problem for us, or whether it literally has to 'find a solution' in order to get into the state it gets into, so that principles of computational complexity etc. would be somehow applicable to what it's doing.
- guest2143 8y ago
  My grad school professor was at a bar with a consultant friend who was trying to find the optimal wiring paths for routing expensive electric cables. My professor asked for the change in his pocket: they went to the hardware store and got plexiglass, dowel and drill. In the hotel room, the put together a model of the points to connect between the plexiglass sides and dunked it in the soapy hotel tub. the pattern the soap bubbles formed was the shortest path between the electrical tower model.
  - zawerf 8y ago
    I know this as the Euclidean Steiner Tree problem: https://en.wikipedia.org/wiki/Steiner_tree_problem https://en.wikipedia.org/wiki/Steiner_tree_problem There are some videos doing exactly what you described: https://youtu.be/dAyDi1aa40E?t=95 https://youtu.be/dAyDi1aa40E?t=95
  - westoncb 8y ago
    Okay, that makes sense to me—we can set up the physical system's initial conditions to mirror some problem we want solved, then let it do its thing and grab the solution back afterward. That definitely feels better justified than the view I had of it, though it still has some weakness, I think. From my understanding the justification for calling it computation comes down to: we can use the physical system to solve a problem that we would ordinarily approach computationally, therefore it must be computing too. Right?
    - stevenhuang 8y ago
      > From my understanding the justification for calling it computation comes down to: we can use the physical system to solve a problem that we would ordinarily approach computationally, therefore it must be computing too. Right? To me, it feels like the intention of "computation" as used here is to give us a convenient way to describe what the physical system _appears_ to be doing (solving something the only way we know how--computationally) as opposed to saying: the rules of our universe influenced these particles to act in such a way that manifested in something interesting to us (an efficient solution to some problem). Very interesting to think then if we can leverage physical systems (specifically non-quantum, to make that more interesting) to solve NP problems.
    - salty_biscuits 8y ago
      It's an analog computer, just not a general purpose one. It solves one problem well.
- JoeAltmaier 8y ago
  Its an analog computer, plain and simple! Just because its not digital, doesn't mean its not 'really computing'
- stevenhuang 8y ago
  > physically solving Seems to me you missed the emphasis on the _physical_ part. I don't see any philosophical quandaries from that since it was clear to me OP was not proposing the bubbles literally computed things.
  - westoncb 8y ago
    That's fair—rereading more closely, their terminology is neutral on the matter. I jumped ahead because typically when I see this brought up that's the main point folks are talking about: since the physical system is 'computing' whatever, then let's get into the limits and capabilities and classifications of the computation etc., skipping over the question of whether it actually should be called 'computation'. It's also just an interesting question imo—so I'd be okay hearing a discussion about it whether the original statement introduced the philosophical quandary or not.

by QML 8y ago

westoncb 8y ago

The main thing I wonder about this is whether it's misleading to say the soap bubble is 'solving' a problem of high computational complexity. If we were to form a description of its state evolving, framed as a computation, then that computation would be in such and such a complexity class—sure. But if you want to go ahead and say that soap bubble is literally computing in the same sense, you're making a number of implicit philosophical commitments that I have yet to see a justification for when this subject is brought up. Edit: to clarify, what I'm getting at is whether we're using it to solve what is a problem for us, or whether it literally has to 'find a solution' in order to get into the state it gets into, so that principles of computational complexity etc. would be somehow applicable to what it's doing.

guest2143 8y ago
My grad school professor was at a bar with a consultant friend who was trying to find the optimal wiring paths for routing expensive electric cables. My professor asked for the change in his pocket: they went to the hardware store and got plexiglass, dowel and drill. In the hotel room, the put together a model of the points to connect between the plexiglass sides and dunked it in the soapy hotel tub. the pattern the soap bubbles formed was the shortest path between the electrical tower model.
- zawerf 8y ago
  I know this as the Euclidean Steiner Tree problem: https://en.wikipedia.org/wiki/Steiner_tree_problem https://en.wikipedia.org/wiki/Steiner_tree_problem There are some videos doing exactly what you described: https://youtu.be/dAyDi1aa40E?t=95 https://youtu.be/dAyDi1aa40E?t=95
- westoncb 8y ago
  Okay, that makes sense to me—we can set up the physical system's initial conditions to mirror some problem we want solved, then let it do its thing and grab the solution back afterward. That definitely feels better justified than the view I had of it, though it still has some weakness, I think. From my understanding the justification for calling it computation comes down to: we can use the physical system to solve a problem that we would ordinarily approach computationally, therefore it must be computing too. Right?
  - stevenhuang 8y ago
    > From my understanding the justification for calling it computation comes down to: we can use the physical system to solve a problem that we would ordinarily approach computationally, therefore it must be computing too. Right? To me, it feels like the intention of "computation" as used here is to give us a convenient way to describe what the physical system _appears_ to be doing (solving something the only way we know how--computationally) as opposed to saying: the rules of our universe influenced these particles to act in such a way that manifested in something interesting to us (an efficient solution to some problem). Very interesting to think then if we can leverage physical systems (specifically non-quantum, to make that more interesting) to solve NP problems.
  - salty_biscuits 8y ago
    It's an analog computer, just not a general purpose one. It solves one problem well.
JoeAltmaier 8y ago
Its an analog computer, plain and simple! Just because its not digital, doesn't mean its not 'really computing'
stevenhuang 8y ago
> physically solving Seems to me you missed the emphasis on the _physical_ part. I don't see any philosophical quandaries from that since it was clear to me OP was not proposing the bubbles literally computed things.
- westoncb 8y ago
  That's fair—rereading more closely, their terminology is neutral on the matter. I jumped ahead because typically when I see this brought up that's the main point folks are talking about: since the physical system is 'computing' whatever, then let's get into the limits and capabilities and classifications of the computation etc., skipping over the question of whether it actually should be called 'computation'. It's also just an interesting question imo—so I'd be okay hearing a discussion about it whether the original statement introduced the philosophical quandary or not.