tag:blogger.com,1999:blog-3722233.post7790408223036906028..comments2019-08-24T01:59:50.579-04:00Comments on Computational Complexity: Boris Trakhtenbrot (1921-2016)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-68344110589920660942016-09-26T13:20:32.299-04:002016-09-26T13:20:32.299-04:00If it is true, as Tony Zee says (in his Quantum Fi...If it is true, as Tony Zee says (in his <i>Quantum Field Theory in a Nutshell</i> and <i>Group Theory in a Nutshell</i>) that <br />------------<br />"any self-respecting physicist should learn about the history of physics, and the history of quantum field theory is among the most fascinating"<br />------------<br />then how much more true is it, that <br />------------<br />"any self-respecting complexity theorist should learn about the history of physics, and the history of P-vs-NP/Perebor theory is among the most fascinating"<br />------------<br />With the above guidance in mind, please allow me to thank <i>Computational Complexity</i> for this fine link to Boris Trakhtenbrot's "A Survey of Russian approaches to perebor (brute-force searches) algorithms" (1984), with its extensive commentary upon Juris Hartmanis' parallel survey "Observations about the Development of theoretical computer science" (1981). <br /><br />These two foresighted surveys provide a binocular view of three decades of subsequent progress in complexity theory, in which we have learned (1) much about the formal obstructions to provably separating class P from class NP, and (2) much about the social obstructions to applying complexity theory to practical problems. <br /><br />In regard to (1), most <i>Computational Complexity</i> readers will require little guidance to the (vast) literature of the past three decades, but in regard to (2), please allow me to commend the binocular view that is supplied by Francis Spufford's <i>Red Plenty</i> (2010) and by Paul Smaldino and Richard McElreath's "The natural selection of bad science" (2016). <br /><br />In particular, Smaldino and McElreath's analysis supplies a necessary counter-weight to the facile rationale of <i>Computational Complexity</i>'s recent essay "Academic rankings foster competition" (September 14, 2016). Yes they do, but it happens too (as Smaldino and McElreath thoroughly document), that competition sometimes foster degradation.<br /><br />In any event, it's completely clear that we all of us owe plenty of appreciation and thanks to researchers like Trakhtenbrot and Hartmanis, for showing us our past sufficiently clearly, as to help us foresee our future (no matter how dimly), and even to help us guide that future hopefully (no matter how imperfectly).John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.com