tag:blogger.com,1999:blog-3722233.post6748297921609096715..comments2020-09-20T19:47:50.963-05:00Comments on Computational Complexity: Mathematics is not commutative Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-72976783711952171242020-09-08T16:20:21.866-05:002020-09-08T16:20:21.866-05:00Here's another potential example of non-commut...Here's another potential example of non-commutativity that I just learned about. In a remarkable lecture, Brendan Guilfoyle speculates that if Simon Donaldson's work on smooth 4-manifolds had come out before Michael Freedman's paper on the 4-dimensional Poincare conjecture, then Freedman's paper in its current form would never have been accepted for publication, because its consequences would have seemed so absurd that referees would have demanded a much more detailed and careful argument. https://youtu.be/VZs1UG2Wtn8?t=2220Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12737691376390596112020-08-24T09:44:45.457-05:002020-08-24T09:44:45.457-05:00I have wondered if the mathematical community had ...I have wondered if the mathematical community had early on adopted dependent choice (DC) rather than the full-blown axiom of choice, and conjectured that "all sets of reals are Lebesgue measurable" (LM), would we now regard ZF + DC + LM (rather than ZFC) as the standard foundation of mathematics? See this answer by Andreas Blass on MathOverflow: https://mathoverflow.net/a/34863Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9119162994934745422020-08-19T08:28:38.677-05:002020-08-19T08:28:38.677-05:00@Lance: Good point. I had almost wanted to say tha...@Lance: Good point. I had almost wanted to say that had we just come up directly with the deterministic version (for Primes), we would not have all these probabilistic results hinging on 'randomness'. This didn't fly quite as well :)Enoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82121164078855544122020-08-17T22:21:26.716-05:002020-08-17T22:21:26.716-05:00AH- excellent point.
I wonder- is coding `M_e(0) d...AH- excellent point.<br />I wonder- is coding `M_e(0) does not halt' into an arithmetic<br />statement hard? So could we NOW give an easier proof of Godel?<br />I think so.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58705821289372835432020-08-17T14:34:52.788-05:002020-08-17T14:34:52.788-05:00I disagree somewhat that if it had been known firs...I disagree somewhat that if it had been known first that HALT is undecidable then Godel's theorem would have been easy. The proof you gave is implicitly using the fact that statements about Turing machines are equivalent to statements in the language of arithmetic. This may seem obvious now, but I think it was genuinely novel at the time and was considered a major part of Godel's breakthrough. It may seem more obvious to us now because working with computers has given us lots of practice translating statements between different languages (e.g. writing compilers and interpreters or even just various kinds of parsers).Patrickhttps://www.blogger.com/profile/09956803907225354566noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91721500115496954812020-08-17T10:28:20.463-05:002020-08-17T10:28:20.463-05:00Evidence for integer factorization is in P: https:...Evidence for integer factorization is in P: https://mathoverflow.net/questions/79366/Steve Huntsmannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81547661754834865152020-08-17T09:01:06.829-05:002020-08-17T09:01:06.829-05:00My favorite example is Primes in P. If it was prov...My favorite example is Primes in P. If it was proven in the 70's instead of the 2000's we wouldn't have had all those partial results (Primes in RP, co-RP, UP, and in P if the generalized Riemann Hypothesis held).Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.com