On 04 Oct 2014, at 07:03, John Clark wrote:
On Wed, Oct 1, 2014 at 9:18 AM, Bruno Marchal <[email protected]>
wrote:
> As I've said no natural phenomenon has ever been found where
nature must solve a NP-hard problem
> To solve it exactly?
Obviously exactly.
> swarm of ants solves efficaciously NP complete problem, like the
traveling salesman problem.
It's not hard to find a pretty good solution to the traveling
salesman problem, but it's next to impossible to find the perfect
one unless the number of cities is very small, impossible for us,
for our computers, for ants, and for nature in general.
> I think some soap film solves some NP problem too,
No they do not. As I pointed out before if you assume that soap
films make use of Real Numbers then yes, soap films can solve a NP
problem, but when the experimental is actually performed it fails to
even come close to doing so. I'll now repeat what I said before.
Scott Aaronson actually tried it and this is what he reports:
"Taking two glass plates with pegs between them, and dipping the
resulting contraption into a tub of soapy water. The idea is that
the soap bubbles that form between the pegs should trace out the
minimum Steiner tree -- that is, the minimum total length of line
segments connecting the pegs, where the segments can meet at points
other than the pegs themselves. Now, this is known to be an NP-hard
optimization problem. So, it looks like Nature is solving NP-hard
problems in polynomial time!
Long story short, I went to the hardware store, bought some glass
plates, liquid soap, etc., and found that, while Nature does often
find a minimum Steiner tree with 4 or 5 pegs, it tends to get stuck
at local optima with larger numbers of pegs. Indeed, often the soap
bubbles settle down to a configuration which is not even a tree
(i.e. contains "cycles of soap"), and thus provably can't be optimal.
The situation is similar for protein folding. Again, people have
said that Nature seems to be solving an NP-hard optimization problem
in every cell of your body, by letting the proteins fold into their
minimum-energy configurations. But there are two problems with this
claim. The first problem is that proteins, just like soap bubbles,
sometimes get stuck in suboptimal configurations -- indeed, it's
believed that's exactly what happens with Mad Cow Disease. The
second problem is that, to the extent that proteins do usually fold
into their optimal configurations, there's an obvious reason why
they would: natural selection! If there were a protein that could
only be folded by proving the Riemann Hypothesis, the gene that
coded for it would quickly get weeded out of the gene pool."
I can agree with this, but the question is not if human can use
nature's solution of an NP-hard (or even a non computable analog
function), but if nature does it. If our consciousness relies on this,
it does not matter that we can't use it. The point, I thought, was
theoretical at the start.
Bruno
By the way I just finished reading Scott Aaronson's book "Quantum
Computing since Democritus" and it's excellent.
John K Clark
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it,
send an email to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
