tag:blogger.com,1999:blog-3722233.post3582196611173810037..comments2024-03-29T08:55:55.727-05:00Comments on Computational Complexity: A Valiant WeekendLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-57855993768308497122011-06-08T20:35:23.524-05:002011-06-08T20:35:23.524-05:00Gromov's article speaks to the topics that Sco...Gromov's article speaks to the topics that Scott's post raises, as follows:<br />--------------<br />At first sight, Nature does not appear exceptionally clever: her evolutionary strategy is not sophisticated, to say the least. But she was selecting from billions upon billions of candidates and her selection criterion, “fit to survive”, may look simple only for a lack of mathematical imagination on our part: an enormous amount of structure goes into this “fit”. Besides, Nature does not run in a structural vacuum—all of physics and chemistry is at her disposal, and she excels in molecular dynamics and in catalysis.<br /><br />Yet, a mathematician might think that Nature is dumb: the primitive mutation/selection mechanism of evolution could not produce anything we, mathematicians, could not divine ourselves.<br /><br />But if so, we inevitably conclude that the human brain, which was cooked up by Nature in the last couple of million years, cannot be especially smart either: all our mathematics, or rather the mathematics-building mechanisms in the brain, must be confined to the rules that evolution had stumbled upon in this relatively short stretch of time and had installed into us.<br /><br />On the other hand, Nature had spent a much longer time (measured by the number of tries involved) in inventing such structural entities as the cell and the ribosome.<br /><br />One may conjecture that neither cell nor brain would be possible if not for profound mathematical “somethings” behind these, Nature’s inventions. But what are these “somethings”? Why do we, mathematicians, remain unaware of them?<br /><br />… Notwithstanding our much-glorified successes, we are, tautologically, blind to what we do not see. (Nature systematically hides from our mind what we are not supposed to know, such as the blind spot in our retina, for instance. The neurological mechanism of this hiding is far from clear.)<br /><br />Also, the history of mathematics shows how slow we are when it comes to inventing/recognizing new structures even if they are spread before our eyes, such as hyperbolic space, for instance.<br />--------------<br /><br />Gromov's paragraphs remind us that all communication channels are two-way … which is of course a valid principle of quantum information theory too.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14861187111356840882011-06-08T07:51:09.948-05:002011-06-08T07:51:09.948-05:00I was at Les's talk and thought it was great! ...I was at Les's talk and thought it was great! I walked out of the room with renewed enthusiasm that complexity theory can and should colonize every other part of science. :-)<br /><br />The way Les put his question was basically this: given that we <i>know</i> from biology, geology, etc. that the evolution of very complicated life took place in "merely" ~3 billion years (rather than, say, 10^100 years), what computational models of "evolvability" can we find, which would render evolution's ability to cut through the exponentially-large search space in that amount of time less surprising? That strikes me as pretty clearly a great scientific question, even if you dislike Valiant's own proposals for how to it.<br /><br />Having said that, I would add that it's partly a matter of taste which numerical facts we choose to be surprised by. So for example, it's <i>also</i> a worthy scientific problem to explain why evolution apparently <i>needed</i> a leisurely 3 billion years, rather than producing humans from RNA soup in a few million years or less!Scotthttps://www.blogger.com/profile/13456161078489400740noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64990183338651016492011-06-06T13:06:35.540-05:002011-06-06T13:06:35.540-05:00Something got wrong, am trying again ...
Here is ...Something got wrong, am trying again ...<br /><br />Here is yet another example to John's comment:<br /><br /><a href="http://www.math.tau.ac.il/~nogaa/PDFS/misbios.pdf" rel="nofollow"> A biological solution to a fundamental distributed computing problem</a>Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40783489014718986972011-06-06T12:51:43.009-05:002011-06-06T12:51:43.009-05:00One more example to John's comment:
http://ww...One more example to John's comment:<br /><br />http://www.math.tau.ac.il/~nogaa/PDFS/misbios.pdfStasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8764500547982606452011-06-06T11:10:34.759-05:002011-06-06T11:10:34.759-05:00Regarding mathematical questions and inspirations ...Regarding mathematical questions and inspirations that arise naturally in the context of biology, Misha Gromov's recent <i>Bulletin of the AMS</i> survey article "Crystals, proteins, stability and isoperimetry" (2011) provides a very readable perspective with dozens of concrete suggestions … certainly biology nowadays provides abundant mathematical inspiration (especially if your name is "Gromov" or "Valiant").John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.com