Professor Stephen A. Cook is a pioneer of the theory of computational complexity. His work on NP-completeness and the P vs. NP problem remains a central focus of this field. Cook won the 1982 Turing Award for "his advancement of our understanding of the complexity of computation in a significant and profound way." This volume includes a selection of seminal papers embodying the work that led to this award, exemplifying Cook's synthesis of ideas and techniques from logic and the theory of computation including NP-completeness, proof complexity, bounded arithmetic, and parallel and space-bounded computation. These papers are accompanied by contributed articles by leading researchers in these areas, which convey to a general reader the importance of Cook's ideas and their enduring impact on the research community. The book also contains biographical material, Cook's Turing Award lecture, and an interview. Together these provide a portrait of Cook as a recognized leader and innovator in mathematics and computer science, as well as a gentle mentor and colleague.
Author(s): Bruce M Kapron (editor)
Series: ACM Books
Edition: 1
Publisher: ACM Books
Year: 2023
Language: English
Commentary: Publisher PDF | Published: 23 May 2023
Pages: 425
City: New York, NY
Tags: Logic; Automata; Computational Complexity; NP-completeness; Theorem-Proving Procedures; Propositional Proof Systems; Propositional Calculus; Parallel Computation
Logic, Automata, and Computational Complexity
Contents
Introduction
Note on formatting and typesetting
Acknowledgments
I BIOGRAPHICAL BACKGROUND
1 Stephen Cook: Complexity's Humble Hero
1.1 Growing Up: Buffalo and Cows
1.2 The Lure of Mathematics
1.3 From Smooth Sailing to Rough Waters
1.4 Growing Roots, Making Waves
1.5 The Quiet Influencer
1.6 Profound and Complex
2 ACM Interview of Stephen A. Cook by Bruce M. Kapron
II THE TURING AWARD LECTURE
3 The 1982 ACM Turing Award Lecture
Abstract
1 Early Papers
2 Early Issues and Concepts
3 Upper Bounds on Time
4 Lower Bounds
4.1 Natural Decidable Problems Proved Infeasible
4.2 Structured Lower Bounds
4.3 Time–Space Product Lower Bounds
4.4 NP-Completeness
4.5 #P-Completeness
5 Probabilistic Algorithms
6 Synchronous Parallel Computation
7 The Future
Acknowledgments
References
III PERSPECTIVES ON COOK'S WORK
4 Cook's NP-completeness Paper and the Dawn of the New Theory
4.1 History
4.2 Cook's Other 1971 Paper
4.3 The Paper at the 3rd STOC
4.4 The Mystery of Section 4.3
4.5 Aftermath
5 The Cook–Reckhow Definition
5.1 Definition of Proof Systems
5.2 Simulations among Proof Systems
5.3 Hard Tautologies and the PHPn Formula
Acknowledgments
6 Polynomially Verifiable Arithmetic
6.1 Introduction
6.2 The Equational Theory PV for Polynomial Time Computability
6.3 Extended Resolution and PV
6.4 Subsequent Developments
Acknowledgments
7 Towards a Complexity Theory of Parallel Computation
7.1 First Words
7.2 The Early Years
7.3 The Beginnings of a Theory
7.4 Development and Issues with the Theory
7.5 Steve's Class and Nick's Class
7.6 Cook's Surveys of Parallel Computation
7.7 Last Words
8 Computation with Limited Space
8.1 Time and Space Bounds
8.2 Pebbling
8.3 Circuits
8.4 Branching Programs
IV SELECTED PAPERS
9 The Complexity of Theorem-Proving Procedures
Summary
1 Tautologies and Polynomial Re-Reducibility
2 Discussion
3 The Predicate Calculus
4 More Discussion
References
10 Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
Abstract
Key words and phrases
CR Categories
1 Introduction
2 Time-Bounded Computers
3 Other Machine Models
4 The Main Theorem
4.1 Algorithm for M2
5 Applications of the Main Theorem
6 Conclusion and Open Questions
Acknowledgment
References
11 The Relative Efficiency of Propositional Proof Systems
1 Introduction
2 Frege Systems
3 Natural Deduction Systems
4 Extended Frege Systems
5 The Substitution Rule
References
12 Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version)
1 Introduction
2 The System PV
Rules of PV
3 The System PV1
4 The Gödel Incompleteness Theorem for PV
5 Propositional Calculus and the Main Theorem
6 Propositional Formulas Assigned to Equations of PV
6.1 Semantic Correctness of propm
7 PV as a Propositional Proof System
8 Conclusions and Future Research
Acknowledgments
References
13 Towards a Complexity Theory of Synchronous Parallel Computation
Abstract
1 Introduction
2 Circuits and Alternating Turing Machines
3 Log Depth vs Log Space
4 Conglomerates and Aggregates
5 Hardware Modification Machines
6 Other Modifiable Models
7 Simultaneous Resource Bounds
8 Open Questions
Acknowledgement
References
14 A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
Abstract
Key words
1 Introduction
2 The Formal Model and an Outline of the Proof
3 The Proof of the Main Lemma
4 Proof of the Main Theorem
5 Conclusion
Acknowledgment
References
15 Pebbles and Branching Programs for Tree Evaluation
1 Introduction
1.1 Summary of Contributions
1.2 Relation to Previous Work
1.3 Organization
2 Preliminaries
2.1 Branching Programs
2.2 One Function Is Enough
2.3 Pebbling
3 Connecting TMS, BPS, and Pebbling
4 Pebbling Bounds
4.1 Previous Results
4.2 Results for Fractional Pebbling
4.3 White Sliding Moves
5 Branching Program Bounds
5.1 The Nec̆iporuk Method
5.2 The State Sequence Method
5.3 Thrifty Lower Bounds
6 Conclusion
Acknowledgments
References
V THE BERKELEY NOTES
16 Cook's Berkeley Notes
17 A Survey of Classes of Primitive Recursive Functions
1 Basic Notions
Relations vs. functions
Cofinal Classes
Explicit Transformation
Substitution
Boolean Operations
Bounded (i.e. limited) quantification
Bounded (i.e. limited) recursion
m-adic notation
Bounded (i.e. limited) recursion on notation
Subpart quantification
2 The Grzegorczyk Hierarchy
Notation
3 Computation Time and Limited Recursion on Notation
Extended Positive Rudimentary Functions, L+.
4 The Ritchie Hierarchy
5 Other Classes
Notation
The Strictly m-rudimentary relations
The positive m-rudimentary relations
The Strongly m-rudimentary relations
The m-rudimentary relations
The constructive arithmetic relations
The extended positive m-rudimentary relations
A context-sensitive language
Spectra
6 Summary of Facts and Open Questions
Closure under operations of relation classes
Functions
References
18 Further Reading
Bibliography
Bibliography of the Works of Stephen A. Cook
1965
1966
1968
1969
1970
1971
1972
1973
1974
1975
1976
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2009
2010
2011
2012
2013
2014
2016
2017
References
Contributors' Biographies
Index
