tag:blogger.com,1999:blog-3722233.post2959222585780083759..comments2020-01-16T02:41:14.513-05:00Comments on Computational Complexity: ScoopedLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-78271219876344094502019-03-28T15:19:09.340-04:002019-03-28T15:19:09.340-04:00As a suitable subject for future Computational Com...As a suitable subject for future <i>Computational Complexity</i> essays, please allow me to suggest the Extended Church-Turing Thesis (ECT). <br /><br />As a start, Boaz Barak's online textbook-in-progress <i>Introduction to Theoretical Computer Science</i> (available on-line) summarizes the present ECT consensus as follows:<br />-----------<br />In the last hundred+ years of studying and mechanizing computation, no one has yet constructed a scalable computing device (or even gave a convincing blueprint) that violates the extended Church Turing Thesis. That said, as we mentioned before quantum computing, if realized, does pose a serious challenge to this thesis. However, even if the promises of quantum computing are fully realized, it still seems that the extended Church-Turing thesis is fundamentally or "morally" correct, in the sense that, while we do need to adapt the thesis to account for the possibility of quantum computing, its broad outline remains unchanged.<br />-----------<br />Barak's broad outline of the ECT encompasses (for example) the cognitive themes that Sanjeev Arora's plenary lecture at the 2018 ICM "The mathematics of machine learning and deep learning " articulates as follows (beginning at 57m20s):<br />-----------<br />"We have very little idea at an operational level of how humans think … in fact, machine learning is currently the best hope for learning how humans think … This is the hottest trend in academia: apply machine learning to discipline "X" … Machine learning speaks to age-old wonders and mysteries … it's a new way of looking at the world, via complicated inexact descriptions that we embrace … a new frontier for knowledge and math …I am optimistic that deep-learning methods can be mathematically understood and/or simplified."<br />-----------<br />Arora's views are consonant, in turn, with this year's Turing Award to (in alphabetical order) Yoshua Bengio, Geoffrey Hinton, and Yann LeCun; an award due in large measure to these researchers' development and practical application of efficient back-propagation algorithms. That this particular Turing Award is well-received amounts to a ECT-centric consensus appreciation that: (1) in practice, "merely polynomial" algorithmic speedups can be scientifically and strategically transformational, and (2) fresh insights into age-old "soft" questions like "how are mathematical ideas conceived?" can be comparably transformational to fresh insights into rigorously logical questions like "how are mathematical ideas validated?".<br /><br />As yet another perspective, ultra-orthodox Quantum Supremacists — are there any? — can cite rigorously logical reasons to dismiss this particular Turing Award as "hype", in the sense that these researcher's back-propagation algorithms for network-training afford a mere polynomial speedup. <br /><br />No such criticisms of this year's Turing Award are heard (that I know of anyway) … and this consensus assent itself is broadly consonant with Boaz Barak's assertion (cited above) that "the extended Church-Turing thesis is fundamentally or 'morally' correct". <br /><br />In summary, then, the Extended Church-Turing Thesis affords plenty of material for discussion here on <i>Computational Complexity</i> (and elsewhere) … and plenty of scope too for reasonable-yet-diverse opinions.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.com