Computational Complexity: Neil Jones (1941-2023)

Eric Allender graciously agreed to put in writing this remembrance of Neil Jones.

Neil Jones handed away on March 27.

Neil’s work had a profound affect on the sector of computational complexity concept, though he was primarily identified for his work in different areas of pc science.  For instance, his 1998 ACM Fellow quotation is “For excellent contributions to semantics-directed compilation, particularly partial analysis, and to the speculation of computation, formal fashions and their sensible realization.”  Notice that there isn’t any point out of “complexity” (besides as it’s bundled along with “concept of computation” — and Jones additionally printed within the space of computability concept).

So what have been some ways in which Neil influenced the event of computational complexity concept?

In 1972, within the 4th STOC convention, Neil collaborated with Alan Selman, to indicate {that a} notion that logicians had been learning because the 1950’s coincided precisely with a pure complexity class.  Extra particularly, given a logical components F, the “spectrum” of F is the set of numbers {n : F has a finite mannequin of measurement n}.  What sorts of units may be the spectrum of a first-order components?  Is that this class of units closed underneath complement?  These have been among the questions that logicians had struggled with.  Jones and Selman gave a exact characterization, as NE (nondeterministic exponential time).  Thus the complement of each spectrum is a spectrum if and provided that NE=coNE.  As D. Sivakumar factors out in a LinkedIn touch upon Neil’s loss of life: “The next yr, Fagin proved that generalized spectra coincide with NP, and descriptive complexity concept was born.”

After all, lots of different issues have been taking place within the late 60’s and early 70’s:  Savitch proved Savitch’s Theorem.  The primary NP-completeness outcomes appeared.  It seems that a number of individuals have been making an attempt to construct on Savitch’s theorem, to indicate that all the pieces in P may be accomplished in log² area, and this motivated Steve Cook dinner to outline an issue (“Path Methods”) and present (1) sure algorithms for Path Methods couldn’t be carried out in small area, and (2) Path Methods has a small-space algorithm iff all the pieces in P does.  This results of Cook dinner’s was related in taste to a theorem of Savitch, exhibiting that an issue he referred to as “Threadable Mazes” was in L if and provided that NL=L.  Though these notions have been clearly within the air, Jones (and — concurrently — Meyer & Stockmeyer) have been the primary to explicitly formalize the notion of logspace reducibility (together with closure underneath composition), and to note that the NP-completeness outcomes of Cook dinner and Karp held additionally underneath logspace reducibility.  And Jones was the primary one to go forward and develop the final concept of logspace reducibility and the speculation of completeness for subclasses of P (first for P itself (with Laaser), and later for NL (with Laaser and Lien)).  I feel that that is when individuals began to get the concept that completeness was not a particular property that just a few issues shared.  Slightly: Practically EVERY pure computational downside was more likely to be full for some cheap complexity class.

Notably, Jones additionally acknowledged that logspace was overkill, when contemplating reductions.  He additionally wished to have a very restricted notion of reducibility, in order that one might discuss meaningfully about issues being full for L.  To this finish, he outlined “log-rudimentary” reducibility.  This was fairly pure for him, since he had work beforehand on Smullyan’s “Rudimentary Relations”.  However log-rudimentary reductions by no means actually caught on.  As an alternative, after Furst, Saxe, and Sipser kickstarted the research of AC⁰ circuits, a notion of AC⁰ reducibility was developed by Chandra, Stockmeyer, and Vishkin within the mid-1980’s, which turned out to be very helpful in classifying issues as being full in numerous subclasses of P.  A lot later, in 1991, I printed a paper with Vivek Gore, exhibiting that Neil’s log-rudimentary reductions are exactly the identical factor as uniform AC⁰ reducibility.  Thus Neil Jones had the perception to outline and research a notion that might not change into mainstream for one more decade, and which nonetheless offers the most effective device for classifying the complexity of pure issues in subclasses of P.

I solely had the pleasure of assembly Neil as soon as, throughout a go to to Copenhagen in 2004, though we might often alternate some e-mail about subjects in complexity.  It’s fascinating to notice that the newest paper on Neil’s DBLP web page offers with complexity courses.  I have never spent a lot time trying on the paper, however I do see that the authors outline a complexity class that lies between NL and P.  It is perhaps fascinating to see if this class coincides with SAC¹ (also referred to as LogCFL).

I thank Lance and Invoice for encouraging me to put in writing just a few strains about Neil’s significance to the sector.