tag:blogger.com,1999:blog-3722233.post1537749221174732045..comments2020-05-25T04:05:03.716-04:00Comments on Computational Complexity: Combinatorics use to not get any respect. But because of Erdos...Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-6605837316276202722013-07-15T00:14:35.001-04:002013-07-15T00:14:35.001-04:00At the end of the day math is math. If someone giv...At the end of the day math is math. If someone gives proof for some problem in field A via techniques from field B, will we not accept it? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37707079440248787462013-07-12T14:29:05.008-04:002013-07-12T14:29:05.008-04:00Where this ignorance of parents ("pure" ...Where this ignorance of parents ("pure" mathematicians) against their children ("recreational" mathematicians) comes from? Not from real life - parents love children even if (and because) they are so "trivial" :-) Most probably, this comes from the axiom "cute, elegant proof = trivial, easy to come up proof". Unfortunately, this is THE axiom also for many computer scientists (have heard from many of them that combinatorics is too "trivial"). Could, for example, results with cute, elegant (hence, "trivial") proofs go through the "FOCS/STOC filter"? I mean, interesting results, but whose proofs were made by the authors as simple as possible (not simpler, of course). I doubt ... So, it will tent for a while until ErdÅ‘s' "The Book" has a part about CS. Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81681409637062368952013-07-12T09:41:12.605-04:002013-07-12T09:41:12.605-04:00Looks like combinatorics has also overtaken logic ...Looks like combinatorics has also overtaken logic as the mathematical foundation of cs (a developement which would be much to the regret of J. McCarthy). The P-NP problem is now mainly considered to be a problem of combinatorics and not of logic (recursion theory). And finite model theory is logic on the surface, but combinatorics in the workings. Clearly the fields of logic and combinatorics are not disjoint, but it looks like cs-logic is becoming more combinatorial than the other way round. By the way, also logic is also at the bottom of the hierarchy of respected mathematical fields. And Cohen was the only mathematician (many say that he was not even a true scotsman, sorry, I meant true logician) who was awarded a fields medal for his work in logic.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17250473486145857052013-07-11T22:10:48.131-04:002013-07-11T22:10:48.131-04:00Um, I'd say P vs NP does not "belong"...Um, I'd say P vs NP does not "belong" to combinatorics - and hence probably can't be used to strengthen the argument for interesting problems in combinatorics - but belongs to computation(al complexity), which is not just a subfield of combinatorics.<br /><br />Also, although computer scientists (including myself) nearly all view combinatorics as important because it is the "right" underlying math for computation, I'm not sure if this is viewpoint is quite as universal amongst "mainstream" mathematicians (analysts, algebraists, topologists, geometers, dynamicists, ...), many of whom also view computer science with some disdain. However, combinatorics is of increasing importance in many fields of mathematics, viz. simplicial sets in algebraic topology, symbolic dynamics, algebraic combinatorics in commutative algebra and representation theory, and I'm sure there are many more examples.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66576962691092115912013-07-11T18:09:26.597-04:002013-07-11T18:09:26.597-04:00also more about the historical context/progess/tre...also more about the historical context/progess/trend of acceptance of combinatorics from another angle, [automated] mathematical proofs, in <a href="http://vzn1.wordpress.com/2013/05/03/adventures-and-commotions-in-automated-theorem-proving/" rel="nofollow">adventures & commotions in automated theorem proving</a>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35374237650647867712013-07-11T14:59:01.466-04:002013-07-11T14:59:01.466-04:00no true scotsman fallacy is also known as "mo...no true scotsman fallacy is also known as "moving the goalposts" & happens in technology fields [eg CS] where technology moves quickly. its also an example of a kuhnian paradigm shift in the technical/mathematical sciences. for more on the changing status of combinatorics over time, see also <a href="http://vzn1.wordpress.com/2013/03/29/erdos-100-tribute-to-a-brilliant-contrarian/" rel="nofollow">Erdos 100, tribute to a brilliant contrarian</a><br />Anonymousnoreply@blogger.com