tag:blogger.com,1999:blog-3722233.post6345573786627432477..comments2024-11-08T03:03:09.702-06:00Comments on Computational Complexity: The Ugly ProofLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-3722233.post-81938272616715932902009-02-11T22:00:00.000-06:002009-02-11T22:00:00.000-06:00Doron Zeilberger has a lot of rants in favor of ug...Doron Zeilberger has a lot of rants in favor of ugly proofs. Here is one giving the general idea:<BR/><BR/>http://www.math.rutgers.edu/~zeilberg/Opinion90.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72339195560315321092009-02-10T20:57:00.000-06:002009-02-10T20:57:00.000-06:00This comment has been removed by the author.par...alogoshttps://www.blogger.com/profile/17177721447465588224noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58581716109803452952009-02-10T19:21:00.000-06:002009-02-10T19:21:00.000-06:00The total number of beautiful proofs may be much l...The total number of beautiful proofs may be much less than the total number of ugly proofs.<BR/>I conjecture that if N is the total number of proofs in this universe, then only O(log(N)) proofs would be considered beautiful.<BR/>This conjecture is probably supported by currently known proofs (which should make a resonable random sample)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64713614697839234712009-02-10T10:49:00.000-06:002009-02-10T10:49:00.000-06:00I thought beauty, like happiness, cannot be sought...I thought beauty, like happiness, cannot be sought directly on purpose.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52855096995859922172009-02-09T04:22:00.000-06:002009-02-09T04:22:00.000-06:00Ugly proof is like ugly code.Should be discouraged...Ugly proof is like ugly code.<BR/>Should be discouraged in general.<BR/>Ugly proofs only for long standing open problems.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14091902421992924002009-02-08T20:28:00.000-06:002009-02-08T20:28:00.000-06:00Mathematics is not about the subjectivity of somet...<I>Mathematics is not about the subjectivity of something as imprecise as "beauty"</I><BR/><BR/>But the point of a proof isn't to convince us that a statement is true; for most major open problems, mathematicians developed a collective intuition about the truth of a statement long before a formal proof came. The point is to give us some insight into <I>why</I> it's true, so we can use that insight to investigate other, similar (or not so similar) problems. And that's one of the yardsticks of mathematical beauty (though by no means the only one).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31352083408850247282009-02-06T16:11:00.000-06:002009-02-06T16:11:00.000-06:00I think that whether or not I'd value an ugly proo...I think that whether or not I'd value an ugly proof depends on what I'd conjectured before the proof was known. If the result is surprising, I don't care if the proof is nice. The (ugly) proof has thus changed my perception of the world. <BR/><BR/>On the other hand, if the ugly proof is of something I (and many others) believe to be true, then the ugly proof still hasn't answered the intuitive question of why is the result true, which is really motivating the need to prove it. Furthermore, the ugly proof is probably of little use in generalizations.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13095735313906307442009-02-06T15:20:00.000-06:002009-02-06T15:20:00.000-06:00A proof is a proof is a proof. Its primary purpose...A proof is a proof is a proof. Its primary purpose is to establish the truth of a statement. One can say that there is a certain beauty in truth itself. <BR/><BR/>Mathematics is not about the subjectivity of something as imprecise as "beauty," although most good mathematicians would recognize it when they see it. Ugly proofs should not be banned because oftentimes they can serve as "shoulders" for the giant, beautiful proofs to stand on.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64978207790587230842009-02-06T13:37:00.000-06:002009-02-06T13:37:00.000-06:00When you actually care about the question, the ugl...When you actually care about the question, the ugliness of the proof doesn't matter (unless you need to implement it, and the algorithm itself is ugly).<BR/><BR/>When you care about the <EM>answer</EM> more than the <EM>question</EM>, then an ugly proof can be dismissed more easily. Of course, people will disagree about whether a proof is ugly or not.<BR/><BR/>For example, I consider Ladner's proof that there are languages in NP that are not NP-complete to be ugly and unsatisfying. I guess I don't care whether such languages exist but would be more interested to know of "interesting" examples of such languages.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26593562077737776622009-02-06T12:12:00.000-06:002009-02-06T12:12:00.000-06:00I think that it often goes the other way. Given:...I think that it often goes the other way. Given:<BR/><BR/>(1) a simple and beautiful non-constructive proof of the existence of an object, or<BR/><BR/>(2) an ugly constructive one that shows very precisely what such an object must be like,<BR/><BR/>which is better? I'd say that the latter gives much more insight - the exact opposite of your claim.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7457857866390275812009-02-06T11:52:00.000-06:002009-02-06T11:52:00.000-06:00I believe that an ugly proof can open the way to t...I believe that an ugly proof can open the way to the discoverty of a really marvelous proof, one that deserves its place in "the book". This is especially important when whe do not know the answer of a big open question and an ugly proof finally asserts it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28139426976003526042009-02-06T11:34:00.000-06:002009-02-06T11:34:00.000-06:00Nice questions have pretty answers. I don't think ...<I>Nice questions have pretty answers. </I><BR/><BR/>I don't think that opinion is supported by the facts. <BR/><BR/>Thanks to Robertson and Seymour, we now know of a vast class of problems (predicates over graphs closed under minors) which are interesting (say four coloring of planar graphs) and have no pretty answers.<BR/><BR/>Similarly, the breakthrough algorithm of Bender and Farach-Colton for LCA also has a case analysis component which while not particularly ugly it is certainly not common. In my opinion, this makes their result all the more remarkable. It is a heavily cited paper, so clearly the result is considered important.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35488674997184977342009-02-06T11:03:00.000-06:002009-02-06T11:03:00.000-06:00My "math camp" instructor insisted, "We don't prov...My "math camp" instructor insisted, "We don't prove things to establish truth." (The implication was that we prove to <I>understand</I>, not to get from point A to point B.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84442340075981561002009-02-06T10:00:00.000-06:002009-02-06T10:00:00.000-06:00Is the proof of the Robertson-Seymour theorem on g...Is the proof of the Robertson-Seymour theorem on graph minors ugly or beautiful?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1772799039600315042009-02-06T09:54:00.000-06:002009-02-06T09:54:00.000-06:00A boring case analysis sounds like something that ...<I>A boring case analysis</I> sounds like something that can be automated, and that may be fun. <BR/><BR/>I know of two areas that take this approach: software verification (e.g., Spec#) and computer algebra systems (e.g., A=B).rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.com