tag:blogger.com,1999:blog-3722233.post5028152903055895215..comments2024-02-29T15:59:22.700-06:00Comments on Computational Complexity: Celebrating Maths in OxfordLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-62429702240452102902014-03-13T00:05:19.482-05:002014-03-13T00:05:19.482-05:00http://mathoverflow.net/q/160099/34859 Any viewshttp://mathoverflow.net/q/160099/34859 Any viewsdisobeyhttps://www.blogger.com/profile/00494166397514627644noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55860152146971283592013-10-05T11:37:24.589-05:002013-10-05T11:37:24.589-05:00Anonymous, thank you for that link to Tim Gowers&#...Anonymous, thank you for that link to Tim Gowers' mathematical essay. Students, in particular, may enjoy too Tim Gowers' remarks — along with remarks by Martin Rees and Steven Hawking — in the video essay <i><b><a href="http://www.sms.cam.ac.uk/media/1216412" rel="nofollow">The Isaac Newton Institute for Mathematical Sciences</a></b></i>.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9735140212793516212013-10-05T10:53:45.437-05:002013-10-05T10:53:45.437-05:00Anonymous, I agree with you regarding the virtue o...Anonymous, I agree with you regarding the virtue of concision … and yet the tide of modern mathematics flows strongly against us both. <br /><br />Consider for example the page upon which the mathematical notion of "smoothness" is defined:<br /><br />• John Milnor's (lucid; classic) monograph <i>Singular Points of Complex Hypersurfaces</i> (1968): page 3.<br /><br />• Ravi Vakil's (justly praised; free-as-in-freedom; often-hilarious) monograph <b><a href="http://math216.wordpress.com/2011-12-course/" rel="nofollow"><i>Foundations of Algebraic Geometry</i></a></b> (2013): page 321.<br /><br />To paraphrase Mark Twain: "Any calm person, who is not blind or idiotic, can see that the mathematical notion of 'smoothness' is hundreds of times more subtle and complicated than we conceived it fifty years ago!"<br /><br />Given the ubiquity of mathematics in engineering, it's amazing that engineering degree programs finish in four short years, both then and now. It is natural to wonder: <b><a href="http://www.youtube.com/watch?v=Wx5I7uEEEYo" rel="nofollow">How does that work exactly</a>?</b>John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58696706557314184552013-10-05T05:59:16.394-05:002013-10-05T05:59:16.394-05:00But we may learn something about how NOT to prove ...But we may learn something about how NOT to prove that P ≠ NP here:<br /><br />http://gowers.wordpress.com/2013/10/03/how-not-to-prove-that-p-is-not-equal-to-np/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1105470533812720302013-10-04T23:27:12.872-05:002013-10-04T23:27:12.872-05:00@John, i luv ur long responses, though it'll b...@John, i luv ur long responses, though it'll be nice if they come in a more digestable fashion for readers. #comments #keepITshortAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24886886578066727292013-10-04T02:56:29.250-05:002013-10-04T02:56:29.250-05:00Elementary today one-upped Numb3rs with the Season...Elementary today one-upped Numb3rs with the Season 2 episode 2 <a href="http://www.cbs.com/shows/elementary/video/EC872537-85AE-1FD4-C2EF-7A8CD60980F2/elementary-solve-for-x/" rel="nofollow">Solve for X </a> which has P vs NP as a fundamental piece of the plot. They even explain the problem well, though confuse its solution with proving P=NP, whose consequences they do get somewhat right. Some cringe-worthy moments but much better than I expected.Paulnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46549358390991784572013-10-03T17:27:58.612-05:002013-10-03T17:27:58.612-05:00HUGE APPRECIATION to landon clay re his decision t...HUGE APPRECIATION to landon clay re his decision to fund mathematics and the P vs NP problem prize in particular. [I too was inspired by wiles and had toyed with FLT significantly prior to the proof.] green with envy at the historic meeting of minds going on. is it being videotaped? if not, maybe the next one?<br />"In complexity, we're still searching for that true path towards P ≠ NP."<br />I would argue "we" have made major progress toward P vs NP but the community is highly self-critical, but also diffuse and <a href="http://vzn1.wordpress.com/2012/12/08/outline-for-a-np-vsppoly-proof-based-on-monotone-circuits-hypergraphs-and-factoring/" rel="nofollow">unable to coalesce around certain promising directions</a>...vznhttp://vzn1.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9085303819976790892013-10-03T13:33:52.632-05:002013-10-03T13:33:52.632-05:00Per the Proceedings of SAT Competition 2013:
----...Per the <b><i><a href="http://satcompetition.org/2013/" rel="nofollow">Proceedings of SAT Competition 2013</a>:</i></b><br /><br />------------<br />PREFACE: The area of Boolean satisfiability (SAT) solving has seen tremendous progress over the last years. Many problems (e.g., in hardware and software verification) that seemed to be completely out of reach a decade ago can now be handled routinely.<br />------------<br /><br />If we adopt a pragmatical/engineering perspective,then the key question in complexity theory is not "How can we rigorously decide PvNP?" (or alternatively, show that this question is undecidable for oracle-decided complexity-class membership), but rather "For how many years/decades/generations will solvers & simulators continue to demonstrate Moore's Law improvements in capability"?<br /><br />In this regard, please let me commend Scott Aaronson's just-opened question on <i>TCS StackExchange</i> <b><a href="http://cstheory.stackexchange.com/questions/19256/overarching-reasons-why-problems-are-in-p-or-bpp" rel="nofollow">Overarching reasons why problems are in P or BPP</a>.</b> Better answers to Scott's implicit question would help substantially in foreseeing means for sustaining (and even accelerating?) the present-day burgeoning of solver & simulator capabilities.<br /><br />Also recommended is the ongoing discussion of the complexity of BosonSampling simulation & verification that Scott has been <b><a href="http://www.scottaaronson.com/blog/?p=1552" rel="nofollow">hosting on <i>Shtetl Optimized</i>.</a></b> Recent BosonSampling investigations extend and deepen the much-discussed complexity theory question that Scott introduced <b><a href="http://arxiv.org/abs/quant-ph/0507242" rel="nofollow">Are Quantum States Exponentially Long Vectors?</a></b> (2005):<br /><br />--------------<br /><b>Q</b> What criterion separates the quantum states we’re sure we can prepare, from the states that arise in Shor’s factoring algorithm? <br /><br />I call such a criterion a “Sure/Shor separator.”<br />--------------<br /><br />Nowadays it is natural to replace in Scott's question "Shor’s factoring algorithm" with "BosonSampling experiments". As an aside, the sardonic temptation to similarly replace “Sure/Shor separator states" with "Sure/BS separator states" should (as it seems to me) be adamantly resisted, if only because these lines of investigation have substantial implications for lines of medical research in which the utmost feasible rapidity of progress is desirable; progress that sardonic rhetoric serves only to impede. <br /><br />With broader regard to the crucial role of both complexity theory and systems engineering in enabling new 21st century enterprises, more valuable than a working/scalable BosonSampling experiment, and more valuable even a working/scalable quantum computer, would be working/scalable techniques for simulating verification-passing BosonSampling datasets (and many other real-world quantum dynamical systems) with resources in P.<br /><br /><b>Conclusion</b> It is well to keep in mind <b><a href="http://www.phpsimplex.com/en/Dantzig_interview.htm" rel="nofollow">George Dantzig's maxim</a>:</b> "In brief, one's intuition in higher dimensional space is not worth a damn!" John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-440024032893959082013-10-03T06:45:28.242-05:002013-10-03T06:45:28.242-05:00Great post and an exciting event! Are there videos...Great post and an exciting event! Are there videos from the talks?Billynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8428830466350945622013-10-03T06:40:09.381-05:002013-10-03T06:40:09.381-05:00If you want to see various important (so people ar...If you want to see various important (so people are already working on them) problems in math solved, and you have LOTS of money, what is more effective:<br />(1) Prize money, or (2) sponsoring workshops, or (3) funding grad students, (4) funding professors, (5) funding others (HS students, Ugrads).<br /><br />Prize money gets the problems out there and is good for the very long term.<br />(Many more kindergardeners know about the Hodge Conjecture because of the<br />Mil prizes.) All the ways to spend the money are good, though I would try to make<br />the grants easy to apply for. Whats better? I would guess you need all of the above.<br /><br />Other fields seem to make progress while P vs NP remains unsolved. Oh well.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.com