Stephen A. Cook is well-known for his pioneering work in computational complexity and many results that he has obtained in this field. While everybody knows that he formulated the fundamental and apparently very difficult question if
$P=NP$
, his other work in theoretical computer science is not so well-known among researchers who are not part of this community. In particular, many people do not know that a large part of his research is connected with mathematical logic. The volume is an attempt to give a glimpse of the wide spectrum of his results, without the aim of being comprehensive, except for the complete bibliography of Cook.
The volume is divided into five parts: I. Bibliographical Background, II. The Turing Award Lecture, III. Perspectives on Cook’s Work, IV. Selected Papers, and V. The Berkeley Notes.
Part I consists of two chapters. The first one is a short biography of Cook, written by Michelle Waitzman, entitled Stephen Cook: Complexity’s Humble Hero. It is certainly interesting to read about life of such a giant scientist, but there is more in the chapter; it also presents the environment in which Cook’s scientific career developed and how the new emerging field was perceived by mathematicians and computers scientists. While computer scientists recognized immediately the importance of the new concepts and ideas, mathematicians were rather skeptical; they viewed it as a “soft” field, one without deep theorems and dealing only with finite structures. But back then, probably nobody expected that problems such as
$P=NP$
? would remain open for another 50 years. The chapter is not only about his scientific carrier, it is also about Cook’s collegial attitude to his students, about sailing, his main hobby, and more. The second chapter is a transcript of an interview of Bruce Kapron with Cook as a Turing Award Recipient. Footnote
1
It nicely complements the previous chapter, as it presents the main biographical events from the point of view of Cook himself.
In Part II, Cook’s survey article An Overview of Computational Complexity is reprinted. The article was based on his Turing Award Lecture. Being written in 1982, it has essentially only historical value, but one can read what was considered important back then and which problems mentioned in the article still remain open (all the fundamental ones, of course, remain).
Part III has five short chapters written by different authors. Each chapter is devoted to particular papers in which Cook made important contributions and how these results influenced further research in the particular subfield of the complexity theory.
The first of these five chapters, written by Christos Papadimitriou, describes the road to the most important paper of Cook, and, perhaps, the most important paper in the entire theoretical computer science literature, The complexity of theorem proving procedures (1971). In this paper Cook formalized and asked the question if
$P=NP$
and proved the existence of
$NP$
-complete problems.
The second chapter, written by Jan Krajíček, focuses on The relative efficiency of propositional proof system (1979) a paper written by Cook and R. A. Reckhow. In this paper they laid foundations of the new field of propositional proof complexity by defining the general concept of a propositional proof system and polynomial simulation of one system by another one. The basic idea is that a propositional proof system is any system that is sound, complete, and for which there is a polynomial time algorithm to check the correctness of a proof.
Another seminal paper of Cook in proof complexity is Feasibly constructive proofs and the propositional calculus (1975), which is the topic of the next chapter written by Samuel Buss. In that paper Cook introduced a equational theory
$PV$
and its first-order conservative extension
$PV1$
, with the intention to formalize reasoning about polynomial time computable functions and relation. In these theories every polynomial time computable function is represented by a term and, moreover, any provably total function defined by a polynomial time computable relation is computable in polynomial time. Thus
$PV$
is naturally associated with the complexity class P (or its functional version
$FP$
). Furthermore, a particular propositional proof system, Extended Resolution (
$ER$
), is also naturally associated with
$PV$
(and
$PV1$
). Later more such pair of complexity classes and theories, and triplets of complexity classes, theories, and proof systems were discovered. Nowadays, for such a pair, we view the theory as a uniform object corresponding to the proof system as the nonuniform version of it.
Many years later, Cook returned to this subject and systematically designed theories for a number of complexity classes. This research culminated in the monograph Logical Foundations of Proof Complexity written with Phuong Nguyen. This book is, however, mentioned only briefly in Buss’s chapter.
Next chapter, written by Paul Beame and Pierre McKenzie, deals with the complexity of parallel computation. Breaking a given computational problem into several tasks that can be solved by independent computers (human or digital ones) working simultaneously is an old idea. Parallel computer architectures had been studied already in the late 1950s. But not all problems can be solved faster using parallelism. The advent of computational complexity provided means to develop a theory of what can be parallelized and what not. Cook’s approach to this problem was based on computations with small space. This eventually led to the thesis: Parallel time is polynomially equivalent to sequential space. In terms of complexity classes the thesis can be stated as parallel-
$P=PSPACE$
. Although this captures the essence of parallel computations, it is not a realistic model; such a polynomial time computation may require an exponential number of processors. Therefore Cook defined a class
$SC$
that reflects better what can be computed efficiently by a parallel computer. It is the class of languages computable in polynomial time and polylogarithmic space (
$\log ^kn$
for some k). (The acronym stands for “Steve’s Class,” in honor of Steve Cook.) An alternative approach, initiated by Allan Borodin, is based on Boolean circuits. According to this view, a fast parallel computation is a computation that can be performed by a small depth circuit. A class
$NC$
similar to
$SC$
is defined as the class of languages accepted by uniform circuits of polynomial size and polylogarithmic depth. These two approaches are not known to be equivalent, in particular, it is open whether
$SC=NC$
.
The last chapter of this part is a very nice historical survey of computation with limited space, written by Nicholas Pippenger. In this area two concepts played important roles in Cook’s research. The first one is pebbling; it is a way to turn problems about space bounded computations to a game in which pebbles are moved on a graph. The number of pebbles corresponds to space needed by the computation. The second one is the branching program, which is a circuit model that captures computations with limited space. I believe that Cook’s motivation for using these concepts was to develop combinatorial methods that would enable him to separate low complexity classes, such as logarithmic space, from higher ones. Although until now nobody succeeded in proving any such separation, Cook and other authors have obtained interesting partial results.
Part IV consists of seven selected papers of Cook; three are with coauthors. Among them there are seminal papers such as the one in which he introduced P,
$NP$
and proved that satisfiability is an
$NP$
-complete problem. Most of the results of these papers are described in Part III; thus, I will not comment on them.
The main chapter of Part V is A Survey of Classes of Primitive Recursive Functions. This is a reprint of Cook’s notes that summarize the material presented in course in Berkeley in 1967. The notes, written before the era of computational complexity, have never appeared in print before. At that time logicians realized that a finer scale was needed than the standard three: non-computable, computable, and primitive recursive functions. Many classes have been defined, but most of them have been forgotten later, because they were well above the ones that we consider interesting today. Part V further contains Cook’s bibliography from 1965 to 2017, references to Part III and short bios of the contributors.
I think it was an excellent idea to edit such a volume in honor of Steven Cook. It is, of course, very difficult to cover all aspects of his scientific career and achievements, but this volume presents a very well balanced choice. I am happy I could contribute to this enterprise at least with this review.
