Oral-History:Juris Hartmanis
About Juris Hartmanis
Juris Hartmanis was born in Latvia in 1928. After the death of his father during World War II, his mother moved the family to Germany, where he received the equivalent of a Bachelor's degree in Physics from the University of Marburg. Then he moved to the United States, where he received Master's degree in Applied Mathematics at the University of Kansas City in 1951 and Ph.D. in Mathematics from Caltech under the supervision of Robert P. Dilworth in 1955. After teaching at Cornell University and Ohio State University, Hartmanis joined the General Electric Research Laboratory in 1958. While at General Electric, he developed many principles of computational complexity theory. In 1965, he became a professor at Cornell University. At Cornell, he was one of founders and the first chairman of its computer science department. With Richard E. Stearns, he received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory."
About the Interview
JURIS HARTMANIS: An Interview Conducted by Andrew Goldstein, Center for the History of Electrical Engineering, July 31, 1991
Interview #120 for the Center for the History of Electrical Engineering, The Institute of Electrical and Electronics Engineering, Inc.
Copyright Statement
This manuscript is being made available for research purposes only. All literary rights in the manuscript, including the right to publish, are reserved to the IEEE History Center. No part of the manuscript may be quoted for publication without the written permission of the Director of IEEE History Center.
Request for permission to quote for publication should be addressed to the IEEE History Center Oral History Program, IEEE History Center, 445 Hoes Lane, Piscataway, NJ 08854 USA or ieee-history@ieee.org. It should include identification of the specific passages to be quoted, anticipated use of the passages, and identification of the user.
It is recommended that this oral history be cited as follows:
Juris Hartmanis, an oral history conducted in 1991 by Andrew Goldstein, IEEE History Center, Piscataway, NJ, USA and Center for the History of Physics, American Institute of Physics, College Park, Maryland.
Interview
INTERVIEW: Dr. Juris Hartmanis
INTERVIEWER: Andrew Goldstein
DATE: 31 July 1991
PLACE: Telephone Interview
[Note: This interview was ended prematurely due to problems with the telephone]
Biographical Background
Goldstein:
I explained in my e-mail the purpose of the project. We are just trying to give details about the nature of your research and some of its impact, the research that was supported by the National Science Foundation. I have a list of some grants that you received from the foundation. It seems like you have been sort of under their steady care since 1967. Can you describe the work you were doing then?
Hartmanis:
Where would you like to start?
Goldstein:
From the beginning. I see the grant titles are fairly vague that they give in the lists, and so if you could just describe with greater precision what it was you were interested in doing.
Hartmanis:
Yes. Let me mention to you that I moved to Cornell in 1965 and was with GE Research Labs before that.
Goldstein:
By way of biographical data, when did you get your doctorate and in what area?
Hartmanis:
I got it at Caltech in mathematics.
Goldstein:
What was the date of your doctorate from Caltech?
Origins of Computational Complexity Theory
Hartmanis:
- Audio File
- MP3 Audio
(120 - hartmanis - clip 1.mp3)
1955. In the last year or two at GE Research Labs, Dick Stearns and I became very much interested in trying to establish quantitative laws that would govern the complexity of computation — how much time, how much memory is needed in computations — and tried to classify computations by resources needed. There was a little bit of preliminary work, but very little. Somewhere around 1964 we started working on it. And to our very great surprise we discovered that, indeed, there were beautiful mathematical theories which you can develop about the complexity of computations. Then we produced our very important paper on the computational complexity of algorithms, which appeared in 1965. I have done lots of other things in between, but my main interest, and almost all of the NSF research support, has been in development of what is called now computational complexity.
Goldstein:
When you say called now —
Hartmanis:
We named the field, Dick Stearns and I. In 1965 I came to Cornell to start the computer science department, and then very soon after I arrived I applied for NSF support, to continue and develop further the work in computational complexity.
Goldstein:
Did you have a specific problem that you were working on?
Hartmanis:
I had many interesting problems. We tried to solve problems which still have not been solved. How hard is it to recognize whether a number is prime or not. And that is a very vital problem for many, many cryptographic problems and so on.
Goldstein:
Did that application exist at the time?
Hartmanis:
Our interest in that was just a very broad kind of understanding, how to measure complexity of computations and how to determine how to get results about them. And at that time Manuel Blum of the Massachusetts Institute of Technology was writing a dissertation on computational complexity and his branch is called abstract or axiomatic computational complexity. Ours was labeled concrete complexity theory. Basically it is not built from axioms, but built around measuring the amount of resources the machines consume. Basically we defined the Turing machine as a basic model and then explored how much resources it takes.
Concept of Computational Complexity Class
Goldstein:
Now, were you working with generalized problems, or did you have specific ones in mind? For instance you mention testing if the number is prime. Were there others, or did you try to work for a class of problems?
Hartmanis:
We introduced the basic concept of computational complexity class: All the computations that can be done in a given resource bound — say, N-square steps where N is the size of the problem. — as the kind of dominant concept in complexity theory. And today everything is expressed in terms of computational complexity classes.
Goldstein:
Measured in terms of N or log N or some power of N.
Hartmanis:
Instead of our old frame in terms of complexity classes. And, as you probably realize, some of the hardest and most important open problems are relations between complexity classes. For example P and NP.
Goldstein:
Exactly.
Hartmanis:
And all those are really of that type.
Goldstein:
Now those are the complexity classes I am familiar with, but are there others?
Hartmanis:
Oodles. We proved the so-called hierarchy results, the first ones, which showed that a slight increase in say the running time, I mean time bound, there was a slight increase, gives you new computations which you cannot do in the earlier bound. So, if you go from N logN in time to N logN in squared time, you get something new which you cannot do in the previous bound. So there is almost one could say a continuum of classes. And very, very important ones. They are now called hierarchies, like the polynomial time hierarchy and all that, which are really just complexity classes defined by different bounds.
Goldstein:
How was that work received by the community? You say you created the field computational complexity.
Hartmanis:
There was some earlier work done. Michael Rabin, for example, wrote on complexity theory, but again, he did not use concrete models, that is, machines. We were beautifully received. You could possibly look up Richard Karp. In 1985 he gave a ACM Turing Award speech, and this is the ACM Communications of February 1986, Volume 29. He reviews the history, and at one point refers to how our paper basically changed the view and suddenly established a field with the right model.
Goldstein:
Right. Which paper is that? Which one was he referring to?
Hartmanis:
The one I did with Stearns. It is published in the 1965 Transactions of the American Mathematics Society.
Role of NSF Funding
Goldstein:
Was it easy to win funding from the NSF for this?
Hartmanis:
We found, or I found at that time, that we were almost encouraged to apply for NSF funding.
Goldstein:
By the foundation itself?
Hartmanis:
Some NSF official visited Cornell for a conference and discussed and encouraged me to do that. So I did. And I have been I think very well treated by the foundation ever since. I think what is also important is that clearly the foundation supported my graduate students. And again, in my Vitae you will see a list of I guess 16 or whatever Ph.D.s who graduated here, and many of these people now are in very good positions, and a number of them have been chairmen of departments or are chairmen of departments and well regarded, recognized scientists. So in this regard the NSF was very, very influential.
Goldstein:
Now when you say that the NSF supported a lot of grad students, that raises a question for me. When you would apply to the NSF for funding, was your budget largely for staff and staff time, or did it include computing time or hardware needs?
Hartmanis:
Clearly that changed as time went on, but basically all we asked for was summer support for the Principal Investigator, me, and then support of graduate students. Probably some partial support, fractional support for a secretary. And now everybody at Cornell who applies for a grant is asked to put in something for computing facilities.
Goldstein:
You mean currently today that is Cornell’s policy?
Hartmanis:
Just to get the service. Because the department has also other NSF grants just for computing equipment. But everybody is taxed. Everybody who can be is taxed, to just support the work stations and the staff who run them.
CER and NSF Grants Compared
Hartmanis:
As a matter of fact, do you deal with such things as the CER grants?
Goldstein:
In the 1980s.
Hartmanis:
They were terribly, terribly important to establish and to move certain departments. Hardly any computing equipment of their own.
Goldstein:
Really? More so than the push to outfit universities with facilities, which was a major NSF initiative in the 1960s.
Hartmanis:
Those clearly are in their impact very, very different animals. Earlier NSF just supported big machines for the whole university. This was not in any sense geared to computer science. When I arrived at Cornell the only equipment here was a big IBM machine.
Goldstein:
As a matter of fact I think it was intended to support computing in other sciences, say chemistry.
Hartmanis:
That is right. Then when the CER grants were established, several universities, Cornell and the University of Washington before that, and Wisconsin and many others, really received a substantial infusion of funds to acquire departmental computing equipment, basic experimental machines for computer science alone. And that had on us, and many, many other schools, a very strong influence. We basically turned from a primarily theoretical work to substantial systems building and experimental work. So that was clearly very, very fundamental.
Growth of Computation Complexity Field
Goldstein:
Let’s return to your work. You said in the late 1970s you launched the area of computational complexity.
Hartmanis:
It is the 1960s. But certainly that work intensified after our first paper appeared in that area.
Goldstein:
Could you be more specific about in what ways?
Hartmanis:
Suddenly publications started appearing in computational complexity. Now there is even a very specialized conference called Structure in Complexity Theory. It was started five or six years ago, and suddenly you could see a growth in a number of papers dealing with complexity issues in computing. Then with my students, I collaborated when I came here with a number of people. We brought John Hopcroft here, with whom I collaborated on different aspects of complexity theory. I collaborated with quite a few people now and then. But really my work then was done mostly with my students. Of the students I had, a number of them have made key contributions which changed or affected the field and all of them were supported by the National Science Foundation. So in that sense there is a very, very important contribution.
Goldstein:
What were some of these key contributions?
Hartmanis:
This is probably not in chronological order, but Lenny Berman and I, we proposed the so-called isomorphism conjecture. The conjecture that all NP complete sets are basically the same set.
Goldstein:
When was that done?
Hartmanis:
Probably 1977 or so.
Goldstein:
So that was the conjecture, and then when was that demonstrated? Or did you do the demonstration?
Hartmanis:
It is still open.
Goldstein:
Really? My understanding was that it is known that if one NP problem is solved then all of them are solved.
Hartmanis:
That is true. If one is solvable in polynomial time, then they all are. But we conjectured much more than that. We conjectured that they are polynomial time isomorphic, which is a strictly defined term, that in structure they are basically identical; that one is just a permutation of another. And in some sense this conjecture could be used to date what is now known as structural complexity theory. And structural complexity theory refers to relating the structure of the different complexity class to each other. So one does not ask about less specific algorithms, but more interested in what are big, more like kind of global, structural relationships. Like the question of do all NP complete sets really look the same or are there different ones.
Goldstein:
Could I ask you to hold on for a minute? The phone has gone soft and I cannot hear you now. Let me see if I can just repair it. Hold on please.
[end of taped interview; checked other side of tape, and it is blank also]
