tag:blogger.com,1999:blog-3722233.post2483962284259650180..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: Beauty and ScienceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-42952712153966624052013-02-17T09:38:19.077-06:002013-02-17T09:38:19.077-06:00Beauty is a funny thing. Like, when we look at the...Beauty is a funny thing. Like, when we look at the pyramids in Egypt do we say "that's a nice set of blocks all well arranged" or do we say "that's a nice pyramid"? But what would we say to someone who doesn't know of a pyramid? We'd have to break the concept down. And the simple (beautiful) statement becomes an understanding of definitions and people may get lost into the weeds of understanding these things. <br /><br />It goes the same way with art or music. Escher's work is beautiful, not only for his abilities but also for the physical limitations that surround it. So can we really appreciate the endless waterfall without actually understanding the impossibility of such a thing?<br /><br />It seems like the concept of beauty can only be appreciated after the ugly ground work has been laid. Once a person studying geometry discovers the need to talk about the three dimensional shape with a polygonal base and sloping sides that meet at a point, then we can start talking about pyramids. But before then its just another abstract concept without a name, or a need to have a name as its undiscovered. Basically once we've done the dirty work, we can go back and erase our mistakes and turn in a more finished work. But if this is so, where is the beauty? In the finished work or in the dirty work that paved the way?AfterMathhttp://www.learninglover.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41374771130619030182013-02-16T21:27:23.515-06:002013-02-16T21:27:23.515-06:00In machine learning a "simple" hypothesi...In machine learning a "simple" hypothesis (likely to generalize with equivalent performance) is merely one that has difficulty shattering the data apriori. It's not necessarily beautiful in any way that would be appreciated by a human. For instance, giant ensembles rule the day on Kaggle, and frankly I would consider them ugly; but it is difficult for a bunch of models put together independently to make completely correlated mistakes, so they are "simple".<br /><br />I think to get to beautiful you have to take "simple" and add "and have utility with respect to humans reasoning about the universe."Paul Mineirohttps://www.blogger.com/profile/05439062526157173163noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56321176954233500142013-02-16T15:57:42.968-06:002013-02-16T15:57:42.968-06:00"In mathematics, not all correct proofs are b..."In mathematics, not all correct proofs are beautiful and not all beautiful proofs are correct." An example of a "beautiful" but incorrect proof in math would be in order (I don't know any). "Beauty" of a proof is not just an aesthetic issue. An ugly proof is like an algorithm "if then , and so on". In contrary, a "beautiful" proof is like a "proof of correctness of this algorithm". It tells *why* the theorem holds, not just that it *holds*. It is no coincidence that none(!) of existing P-NP ugly proofs have found their "beautiful" sisters. Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47967946747523425692013-02-15T15:27:15.463-06:002013-02-15T15:27:15.463-06:00The physicist/historian Derek deSolla Price has ar...The physicist/historian Derek deSolla Price has argued that although the final products of science commonly <i>are</i> polished-and-beautiful gems, the factual ores in which these gems are found commonly is messy indeed. <br /><br />For example, DeSolla Price's essay <i>Of String and Sealing Wax</i> (1963) contains the (unattributed yet much-quoted) passage: "It is not just a clever historical aphorism, but a general truth, that 'thermodynamics owes much more to the steam engine than ever the steam engine owed to thermodynamics.'"<br /><br /><b>Aside</b> DeSolla Price's maxim may originate in the once-celebrated Scottish physicist James Alfred Ewing's 1894 monograph <i>The Steam-Engine and Other Heat-Engines</i>, in which we read:<br /><br />-------<br />"It is remarkable how little the infancy of the steam engine has owed to scientific nursing. […] Unfortunately, however, for its bearing upon practice, while the thermodynamic theory was rigorous in itself, the application of it to steam-engine problems was founded upon certain simplifying assumptions which experience has since shown are far from correct."<br />-------<br /><br />Fortunately for younger 21st century researchers, there is no shortage of ores that by "expanded the <i>explicandum</i> of science in many and almost fortuitous directions" (in Price's celebrated phrase) hold forth reasonable promise of being rich in gem-stones. <br /><br />One grizzled old prospector (as it seems to me) is Juris Hartmanis, who radically expanded the <i>explicandum</i> of complexity theory by noting that "Results about the complexity of algorithms change quite radically if we consider only properties of computations which can be proven formally … These results suggest very strongly that we need to explore further how our 'world view' of the complexity of algorithms has to be changed if we consider only provable properties of algorithms."<br /><br />Similarly, two younger prospectors are Scott Aaronson and Alex Arkhipov, who have radically expanded the <i>explicandum</i> of quantum information theory by asking (implicitly) for polished gem-stone answers to the messy ore-question "Why are there no known scalable schemes for preparing/detecting <i>n</i>-photon states?"<br /><br />If and when, during coming decades, polished scientific explanations are conceived for the Hartmanis and Aaronson/Arkhipov <i>explicandae</i>, very plausibly we will treasure these 21st century explanations as beautiful gems.<br /><br /><b>Conclusion</b> There is at present no shortage of <i>explicandum</i>-ore … and we have some idea of what 21st century's gem-stones that ore may contain … but the gems themselves are (as usual) proving to be mighty difficult to isolate and polish! John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74199576309865997702013-02-15T13:39:52.516-06:002013-02-15T13:39:52.516-06:00I agree with Greg Pfeil's quote. First try to ...I agree with Greg Pfeil's quote. First try to solve the problem, even with an ugly, brutal proof. This is just to convince yourself. Then (and only then) comes the next step: how to convince all others? All who don't want to go through tons of claims, sub-claims, through tons of notations? Fortunately, we (human species) and most of animals are convinced/attracted by the beauty. This is perhaps why most fundamental theorems have deserved beautiful proofs, at least a search for them. Erdős had it lighter: combinatorics is beautiful in its "simplicity". TCS has it harder. Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80308999507940442392013-02-15T13:36:06.793-06:002013-02-15T13:36:06.793-06:00I always have one question in my mind, that is do ...I always have one question in my mind, that is do we really know the truth? I have the original paperback edition of Wittgenstein's book, Tractacus Logico Philosophicus and the book is really a great great masterpiece. He says in a simple language that mathematics is the ultimate truth and therefore there does not exist any field called Philosophy.<br />But, I always believe that Scientific Truth is Beautiful and Elegant.Arka Bhattacharyahttps://www.blogger.com/profile/00801802507777720869noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48928380005499051412013-02-15T13:26:39.828-06:002013-02-15T13:26:39.828-06:00Related (long) essay: http://norvig.com/chomsky.ht...Related (long) essay: http://norvig.com/chomsky.html<br /><br />Amit CAChttps://www.blogger.com/profile/14911233583375020356noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65190844214522570192013-02-15T11:08:22.191-06:002013-02-15T11:08:22.191-06:00I’ve always liked this Bucky quote:
“When I’m wor...I’ve always liked this Bucky quote:<br /><br />“When I’m working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong.”Greg Pfeilhttps://www.blogger.com/profile/03628058891284356327noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47047868509542385192013-02-15T08:20:19.755-06:002013-02-15T08:20:19.755-06:00"In mathematics, not all correct proofs are b..."In mathematics, not all correct proofs are beautiful and not all beautiful proofs are correct."<br /><br />I'll grant you the poetic license but, in mathematics, "proof" implies "correct".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15852732234023726352013-02-15T08:07:07.853-06:002013-02-15T08:07:07.853-06:00No, the language of mathematics is computational a...No, the language of mathematics is computational and thus universal, independent of the particular species that creates it. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23549625791582230282013-02-15T08:03:16.648-06:002013-02-15T08:03:16.648-06:00The language of mathematics is a human constructio...The language of mathematics is a human construction. Are you saying we must fit the language to the "truth" of physics? That by definition, physics and truth should be beautiful, and let's rewrite mathematics 'till it is?Anonymousnoreply@blogger.com