Juris Hartmanis passed away on July 29 at the age of 94

 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.