Gödel's Lost Letter and P=NP

source—wonderful 2015 CACM interview

Juris Hartmanis passed away this morning. He was a professor in Cornell’s computer science department since 1965. He won the 1993 Turing Award with Richard Stearns for their 1963–1965 paper “On the Computational Complexity of Algorithms.”

Today, Dick and I express our condolences and also appreciation for a long life and career shaping our field of computational complexity theory.

One mark of a long life is that the Complexity Theory Retrospective volume honoring his 60th birthday in 1988 was longer ago than the beginning of my tenure-track career at Buffalo in 1989. In the early 1980s, when I met both him and Alan Selman (who edited the volume), they were progenitors of the vein within computational complexity that emphasizes the structure of classes of problems.

I mean “progenitor” quite strongly: When I joined Cornell as a Mathematical Sciences Institute postdoc in 1986, the Computer Science Department generously gave me office space a few doors down from Juris in Upson Hall. I mixed with a gaggle of his students: Lane Hemaspaandra and Jim Kadin and Richard Chang and Desh Ranjan, also saw much of Jin-Yi Cai on his return visits, and had just missed Ming Li and Luc Longpré. We all amplified the energy that Juris brought to the field.

An Echo in Quantum

The structural framework needed to be filled with combinatorial power from other areas of mathematical sciences. But to see the framework’s longevity, one need look no further than the Best Paper in the 2022 Computational Complexity Conference and a paper just accepted to FOCS 2022 that was featured in Quanta:

• “The Acrobatics of BQP” by Scott Aaronson, DeVon Ingram, and William Kretschmer.

• “Verifiable Quantum Advantage Without Structure” by Takashi Yamakawa and Mark Zhandry.

Both are on quantum computing, a field that really began to exist about the time that Juris decided that Pankaj Rohatgi would be his last PhD student. The foci are problems involving Fourier transforms and their correlations, error-correcting codes, and the relationship of randomness to entropy that go well beyond what we thought of as “Structure.” Neither paper cites anything by Juris. Yet the former paper’s results are framed as complexity class relations that jump off the page—here are just three square centimeters of the abstract:

All three results in the latter paper are relative to a random oracle; the first states: “There are NP search problems solvable by BQP machines but not BPP machines.” The expansion of formal machine models from the basic Turing machine, in order to embrace elements of complexity, is the backbone of the paper with Stearns. The relation of machine models to classes in the presence of oracles was the focus of Juris’s ICALP 1986 paper with Lane, “Complexity Classes Without Machines.”

Founding Paper

My pithiest statement of the 1965 paper’s impact is that it made Turing’s tape-machine formulation durable. Indeed, the notions of streaming algorithms, nearly-linear time efficiency, and data locality being one-dimensional that I recall from the 1990s have more affinity to that paper’s technical development than to the polynomial benchmark of feasibility that yielded the formalizations of P and NP either side of 1970. Here are two machine diagrams from the paper:

Before giving the second diagram, let me note that their simple question of whether there is any algebraic irrational number that can be computed to places in time by this kind of machine, has yet to be answered.

The latter diagram conveys their proof of the Time Hierarchy Theorem—though needing a quadratic separation, as today’s logarithmic-gap formulation needed an improvement the following year by Stearns with Frederick Hennie. That is to say, the paper that defined complexity measures also demonstrated how it is possible to prove lower bounds for them.

It Could Have Been Lambdas

Lest you think the machine formulation was inevitable at the start, consider the following comment from “Mathai”—whom I take to be Mathai Joseph—in Lance Fortnow’s 2015 post marking the paper’s 50th anniversary:

“I talked to Hartmanis about this in 2012 and asked if they had considered using recursive function theory. He said they had and it had made things horribly complicated. Then they came across Turing machines and the whole thing became ‘so simple’ !”

I myself once took part in work trying to re-base complexity on recursion in an alteration of the lambda calculus. So many things have earned the name Turing tarpits; theirs based squarely on Turing was not.

Dick Karp, quoted by Stearns in his contribution to the 60th birthday volume, captured the paper’s importance:

[I]t is the 1965 paper by Juris Hartmanis and Richard Stearns that marks the beginning of the modern era of complexity theory. Using the Turing machine as their model of an abstract computer, [they] provided a precise definition of the “complexity class” consisting of all problems solvable in a number of steps bounded by some given function of the input length . Adapting the diagonalization technique that Turing had used to prove the undecidability of the Halting Problem, they proved many interesting results about the structure of complexity classes. All of us who read their paper could not fail to realize that we now had a satisfactory formal framework for pursuing the questions that [Jack] Edmonds had raised earlier in an intuitive fashion.

Dick and I have talked about the importance of good definitions often on this blog, and here is a similar post by Lance. In my formative years, I was fortunate to have two texts that wove theirs and the P-NP-based definitions together: [GJ79] and [HU79].

Undecidability and Proofs

A second vein of Juris’s work made a more particular impression on me, even before I met him. For SWAT (now FOCS) in 1967, he wrote a single-author paper, “On the Complexity of Undecidable Problems in Automata Theory.” The essence is that above a certain level of machine sophistication, whenever you prove the “good news” of lower bounds to separate classes in a hierarchy, you also get the “bad news” of there being problems between the class levels whose status is not resolvable in whatever strong system of logic you employ.

This raises the question, for classes like P and NP that have not yet been separated, whether the logical independence phenomenon washes over the entire landscape. He and John Hopcroft wrote a short paper for SIGACT News outlining this possibility. The topic was taken up by others, including Dick with Rich De Millo and later myself, and continues to percolate.

One of his last papers, “Computational Complexity and Mathematical Proofs,” takes the opposite avenue of how the structure of computations influences the production of proofs, including interactive proofs. This was based on an earlier paper with Chang, Ranjan, and Rohatgi, which I covered in a 2015 post. This diagram conveys the idea:

A Dinner Before Going to NSF

One of my most delightful memories is sitting next to Juris at the conference dinner at the IFIP 1994 congress in Hamburg. Earlier that day I had met the conference honoree, Konrad Zuse, even speaking a little in German with him. We were not seated close to Zuse—indeed, I am not confident to say either way whether he was there. But seated across from us was a woman representing the NSF whom Juris was most interested to talk with.

The strong memory I have is that I did not commandeer the conversation toward technical problems within structural complexity. Juris was eager to convey command and interest in the breadth of Computer Science, and so was I. We three went further: into music and art and culture quite apart from computers. It was a delightful flow of talk for almost two hours. Juris thanked me afterward for not waxing technical. I did not fully get the picture until Juris joined NSF as Director of CISE two years later, in 1996.

There is much more I could say about his work promoting the complexity theory community, about being a founding editor of the Springer-Verlag Lecture Notes in Computer Science series, about helping to found Cornell’s computer science department. On the last, his longtime Cornell colleague Anil Nerode has sent me this:

“I was chairman of the committee of three, which included Bob Walker, that selected him to chair and organize a new computer science department. He already exhibited the scientific and people skills, and the breadth of vision, for which he was later famous. I will miss him very much.”

One other detail I remember of Juris’s personal life is that he liked sporty cars. I am not among those who rode with him muscularly in one—other drivers have filled that niche for me. We invite readers who have done so—or who wish to give any other personal reminiscences—to contribute below. I’ll leave with the observation that of the two scientists in this photo—

“A Great Man and a Statue” source

—it was as much in Juris’s nature to wear a tie as it was for the other guy not to.

Open Problems

Again we give our condolences to his family and surviving colleagues, which set includes the three acknowledged at the end of the 1967 paper mentioned above:

[some small tweaks]