Juris Hartmanis 1928–2022

One thing I learned from the obituary on Scott Aaronson's blog (https://scottaaronson.blog/?p=6622) is that Juris Hartmanis proved in 1965 (as a very early result in his career) that there are infinitely many separate complexity classes (both for time complexity and space complexity) for decidable computational problems.

That is, for every problem that takes a certain amount of computational resources to solve correctly in general, there is always a harder (still solvable) problem that takes asymptotically more resources than that one. There is no hardest problem.

That doesn't necessarily say anything about whether these problems would be of practical interest to human beings, but conceptually, there is an infinite hierarchy of complexity classes, and there can never been an algorithmic discovery that would make all of them equally hard to solve.

https://en.wikipedia.org/wiki/Time_hierarchy_theorem

https://en.wikipedia.org/wiki/Space_hierarchy_theorem

Aaronson says that this guaranteed that "that the [then] new field of computational complexity theory would have a subject matter". He also notes that Richard Lipton and Ken Regan say that Hartmanis actually pioneered the concept of studying problems systematically in terms of the complexity classes they fall into.

Hartmanis's original co-author, Richard Stearns, is still alive.

https://en.wikipedia.org/wiki/Richard_E._Stearns

Juris Hartmanis was Turing award winner laying out foundations for complexity theory. His life in his own words: https://cacm.acm.org/magazines/2015/4/184690-an-interview-wi...

"I also discovered, during my education and early research experience, that you do not have to know that much to do research. With a good background education, one can very quickly absorb the necessary specialized knowledge for a specific research area. I think what Caltech really taught me was to be independent, and to try to go to the essence of a problem."

In some ways a typical(and tragically sad) beginning for Latvian(and other Baltic) refugees at the end of WW2 but quite extraordinary achievements later on.

Also cowrote "Algebraic structure theory of sequential machines" (1966) which —if, along with its successor Krohn-Rhodes theory seems to be largely impractical— is an interesting path-not-taken in CS...

Just saw this news here. He taught me at Cornell when I was a CS undergrad and I remember that class fondly. I still remember one of his office hours which was a day or two before thanksgiving. No one showed up except me and I remember thinking to myself - I am here by myself with a Turing award winner. Unreal!! He was a fantastic professor and person. RIP, professor Hartmanis

name, surname sounds unmistakably Latvian. Turing award... and I didn't even know... rest in peace