Neil Jones (1941-2023)

Eric Allender graciously agreed to write this remembrance of Neil Jones.

Neil Jones passed away on March 27.

Neil's work had a profound impact on the field of computational complexity theory, although he was primarily known for his work in other areas of computer science.  For example, his 1998 ACM Fellow citation is "For outstanding contributions to semantics-directed compilation, especially partial evaluation, and to the theory of computation, formal models and their practical realization."  Note that there's no mention of "complexity" (except as it is bundled together with "theory of computation" -- and Jones also published in the area of computability theory).

So what were some ways that Neil influenced the development of computational complexity theory?

In 1972, in the 4th STOC conference, Neil collaborated with Alan Selman, to show that a notion that logicians had been studying since the 1950's coincided exactly with a natural complexity class.  More specifically, given a logical formula F, the "spectrum" of F is the set of numbers {n : F has a finite model of size n}.  What kinds of sets can be the spectrum of a first-order formula?  Is this class of sets closed under complement?  These were some of the questions that logicians had struggled with.  Jones and Selman gave a precise characterization, as NE (nondeterministic exponential time).  Thus the complement of every spectrum is a spectrum if and only if NE=coNE.  As D. Sivakumar points out in a LinkedIn comment on Neil's death: "The following year, Fagin proved that generalized spectra coincide with NP, and descriptive complexity theory was born."

Of course, a lot of other things were happening in the late 60's and early 70's:  Savitch proved Savitch's Theorem.  The first NP-completeness results appeared.  It appears that several people were trying to build on Savitch's theorem, to show that everything in P can be done in log² space, and this motivated Steve Cook to define a problem ("Path Systems") and show (1) certain algorithms for Path Systems could not be implemented in small space, and (2) Path Systems has a small-space algorithm iff everything in P does.  This result of Cook's was similar in flavor to a theorem of Savitch, showing that a problem he called "Threadable Mazes" was in L if and only if NL=L.  Although these notions were clearly in the air, Jones (and -- simultaneously -- Meyer & Stockmeyer) were the first to explicitly formalize the notion of logspace reducibility (including closure under composition), and to notice that the NP-completeness results of Cook and Karp held also under logspace reducibility.  And Jones was the first one to go ahead and develop the general theory of logspace reducibility and the theory of completeness for subclasses of P (first for P itself (with Laaser), and later for NL (with Laaser and Lien)).  I think that this is when people started to get the idea that completeness was not a special property that only a few problems shared.  Rather: Nearly EVERY natural computational problem was likely to be complete for some reasonable complexity class.

Notably, Jones also recognized that logspace was overkill, when considering reductions.  He also wanted to have a really restricted notion of reducibility, so that one could talk meaningfully about problems being complete for L.  To this end, he defined "log-rudimentary" reducibility.  This was quite natural for him, since he had work previously on Smullyan's "Rudimentary Relations".  But log-rudimentary reductions never really caught on.  Instead, after Furst, Saxe, and Sipser kickstarted the study of AC⁰ circuits, a notion of AC⁰ reducibility was developed by Chandra, Stockmeyer, and Vishkin in the mid-1980's, which turned out to be very useful in classifying problems as being complete in various subclasses of P.  Much later, in 1991, I published a paper with Vivek Gore, showing that Neil's log-rudimentary reductions are precisely the same thing as uniform AC⁰ reducibility.  Thus Neil Jones had the insight to define and study a notion that would not become mainstream for another decade, and which still provides the best tool for classifying the complexity of natural problems in subclasses of P.

I only had the pleasure of meeting Neil once, during a visit to Copenhagen in 2004, although we would occasionally exchange some e-mail about topics in complexity.  It is interesting to note that the most recent paper on Neil's DBLP page deals with complexity classes.  I haven't spent much time looking at the paper, but I do see that the authors define a complexity class that lies between NL and P.  It might be interesting to see if this class coincides with SAC¹ (also known as LogCFL).

I thank Lance and Bill for encouraging me to write a few lines about Neil's importance to the field.