Juris Hartmanis, one of the founders of Complexity Theory, passed away on July 29 at the age of 94. The Gödel's Last Letter blog has an obit posted here. Scott Aaronson has some words and a guest post by Ryan Williams here. When other bloggers post obits I will update this paragraph to point to them.
Here is one non-blog obit: here. For an interview with Juris see here.
Hartmanis and Stearns shared the 1993 Turing award for the paper On the Computational Complexity of Algorithms (see here for the paper and see here for his Turing Award Talk). In that paper they define DTIME(T(n)) for Turing Machines. They also proved some theorems about how changes to the model (1-tape, 2-tape, 1-dim, 2-dim others) change the notion of DTIME(T(n))- so they were well aware that the definition was not robust. They also have some theorems about computable numbers.
We are used to the notion that you can measure how long a computation takes my counting the number of steps on a Turing Machine. Before the Hartmanis-Stearns paper this was not how people thought of things. Knuth (I suspect independently) was looking at what we might now call concrete complexity- how many operations does an algorithm need. Hartmanis-Stearns were beginning what is now called Complexity Theory.
Recall that later, the Cook-Levin Theorem used Turing Machines.
If Hartmanis-Stearns did not start the process of putting complexity on a rigorous mathematical basis how might complexity theory have evolved? It is possible we would not have the Cook-Levin Theorem or the notion of NP. It is possible that we would ASSUME that SAT is hard and use that to get other problems hard, and also do reverse reductions as well to get some problems equivalent to SAT. Indeed- this IS what we do in other parts of theory with assuming the following problems are hard (for various definitions of hard): 3SUM, APSP, Unique Games. And in Crypto Factoring, DL, SVP, and other problems.
Hartmanis did other things as well. I list some of them that are of interest to me - other people will likely list other things of interest to them.
0) He had 21 PhD Students, some of them quite prominent. The list of them is here.
1) The Berman-Hartmanis Conjecture: All NP-Complete sets are poly isomorphic. Seems true for all natural NP-complete sets. Still open. This conjecture inspired a lot of work on sparse sets including that if a sparse set S is btt-hard for NP, then P=NP (proven by Ogiwara-Watanabe)
2) The Boolean Hierarchy: we all know what NP is. What about sets that are the difference of two NP sets? What about sets of the form A - (B-C) where A,B,C are all in NP? These form a hierarchy. We of course do not know if the hierarchy is proper, but if it collapse then PH collapses.
3) He helped introduce time-bounded Kolmogorov complexity into complexity theory, see here.
4) He was Lance Fortnow's undergraduate advisor.
5) There is more but I will stop here.
> Before the Hartmanis-Stearns paper this was not how people thought of thingsReplyDelete
How did people think of things back then?
Good question. I think the following is true but would be happy if someone corrects or modifies:ReplyDelete
People in Logic thought mostly in terms of DECIDABLE/UNDEC
People in Enginnering thought FAST/SLOW.
Hartmanis-Stearns and Knuth helped to bridge that gap and bring rigor to the FAST/SLOW distinction.
People also tried to bring in ‘algebraic’ formalisms to study and to synthesize circuits and automata. Juris had a book with Stearns on the algebraic structure theory of sequential machines. (cf. Krohn-Rhoades theory, Schutzenberger’s theorem torsion-free semigroups). There was some research in ‘simplicity/easiness’ as complexity—for example size of smallest universal Turing machine.Delete
The wiki entry is probably one of the very few ones that hasn't changed in the advent of these news, from 'is' to 'was'.ReplyDelete
Usually you seem change the second news is announced.
People were also interested in algebraic formulations--Juris has a book (with Stearns) on the Algebraic Structure Theory of Sequential Machines. (cf Kron-Rhodes decomposition, Schutzenberger Thm on torsion-free semigroups for work in this direction). Subrecursive hierarchies (Grzegorczyk, Ritchie, etc.) were an attempt to relate "running time complexity" to structure.ReplyDelete
People also were interested in "complexity" as minimum size (e.g. minimum size universal Turing machines).
The idea of counting number of steps to measure complexity does not start with the Hartmanis-Stearns paper--von Neuman already proved operation count bounds for the ENIAC. Edmonds advocated for the distinction between P and NP, as did Cobham.
The set of Hartmanis et al papers was amazing because it suddenly made things clear, mathematical, and, in the best of this meaning -- easy. It changed the way we look at things.
R.I.P , Juris HartmanisReplyDelete
R.I.P , Juris Hartmanis .ReplyDelete