I woke up this morning to two pieces of news. Subhash Khot has
just been named a MacArthur Fellow, the "genius" award, for his work on
unique games. But I also
just learned about Monday's passing of the great Russian theorist Boris Trakhtenbrot at the age of 95.
Trakhtenbrot has a number of important results in automata theory, model theory and logic to name just a few areas. In computational complexity we know him best for the Gap Theorem which he proved independently with Allan Borodin. Roughly the gap theorem states that for any computable f there is a computable time-bound t such that DTIME(t) = DTIME(f(t)), every problem solvable in time f(t) can also be solved in time t. For example there is a time bound t such that DTIME(t) = DTIME(2
t). This doesn't violate the time hierarchy since t may not be time-constructible. There is nothing special about time here, it works for space or any
abstract complexity measure.
Borodin and Trakhtenbrot worked independently because they sat on different sides of the iron curtain during the cold war which very little communication in between. Boris Trakhtenbrot wrote
A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms (
PDF) that traces this early history of Russian theory. He didn't hold back discussing some of the academic politics in Russia that stifled research into computational complexity and gave us a window into the Russian scientific community in the mid-20th century.
Thankfully the iron curtain has been replaced by a global internet and we can do science together. Let's hope it stays that way.
If it is true, as Tony Zee says (in his Quantum Field Theory in a Nutshell and Group Theory in a Nutshell) that
ReplyDelete------------
"any self-respecting physicist should learn about the history of physics, and the history of quantum field theory is among the most fascinating"
------------
then how much more true is it, that
------------
"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"
------------
With the above guidance in mind, please allow me to thank Computational Complexity 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).
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.
In regard to (1), most Computational Complexity 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 Red Plenty (2010) and by Paul Smaldino and Richard McElreath's "The natural selection of bad science" (2016).
In particular, Smaldino and McElreath's analysis supplies a necessary counter-weight to the facile rationale of Computational Complexity'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.
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).