000			05943nam a2200661 i 4500
001			9798400707803
003			ACM
005			20260528133339.0
008			230523s2023 nyu 001 0deng d
020			_a3588287
020			_a9798400707803 _qebook
020			_a9798400707780 _qepub
020			_z9798400707797 _qhardcover
020			_z9798400707773 _qpaperback
024	7		_a10.1145/3588287 _2doi
100	0		_aKapron, Bruce M. _eeditor.
245	1	0	_aLogic, Automata, and Computational Complexity/ _bThe Works of Stephen A. Cook _cBruce M. Kapron.
250			_aFirst Edition
264		1	_a[New York, NY, USA] : _bAssociation for Computing Machinery; _c[2023].
300			_a1 PDF (xxvi, 399pages) _bLuaTEX
490	1		_aACM books, _x2374-6777 ; _v#43
505	8		_a Introduction -- Acknowledgments
505	8		_a PART I BIOGRAPHICAL BACKGROUND
505	8		_a1 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
505	8		_a2 ACM Interview of Stephen A. Cook by Bruce M. Kapron
505	8		_a PART II THE TURING AWARD LECTURE
505	8		_a3 The 1982 ACM Turing Award Lecture -- An Overview of Computational Complexity -- Abstract -- 1 Early Papers -- 2 Early Issues and Concepts -- 3 Upper Bounds on Time -- 4 Lower Bounds -- 5 Probabilistic Algorithms -- 6 Synchronous Parallel Computation -- 7 The Future -- Acknowledgments -- References
505	8		_a PART III PERSPECTIVES ON COOK'S WORK
505	8		_a4 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
505	8		_a5 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
505	8		_a6 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
505	8		_a7 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
505	8		_a8 Computation with Limited Space -- 8.1 Time and Space Bounds -- 8.2 Pebbling -- 8.3 Circuits -- 8.4 Branching Programs
505	8		_a PART IV SELECTED PAPERS
505	8		_a9 The Complexity of Theorem-Proving Procedures -- Summary -- 1 Tautologies and Polynomial Re-Reducibility -- 2 Discussion -- 3 The Predicate Calculus -- 4 More Discussion -- References
505	8		_a10 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 -- 5 Applications of the Main Theorem -- 6 Conclusion and Open Questions -- Acknowledgment -- References
505	8		_a11 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
505	8		_a12 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 -- 7 PV as a Propositional Proof System -- 8 Conclusions and Future Research -- Acknowledgments -- References
505	8		_a13 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 -- Acknowledgment -- References
505	8		_a14 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
505	8		_a15 Pebbles and Branching Programs for Tree Evaluation -- 1 Introduction -- 2 Preliminaries -- 3 Connecting TMS, BPS, and Pebbling -- 4 Pebbling Bounds -- 5 Branching Program Bounds -- 6 Conclusion -- Acknowledgments -- References
505	8		_a PART V THE BERKELEY NOTES
505	8		_a16 Cook's Berkeley Notes
505	8		_a17 A Survey of Classes of Primitive Recursive Functions -- 1 Basic Notions -- 2 The Grzegorczyk Hierarchy -- 3 Computation Time and Limited Recursion on Notation -- 4 The Ritchie Hierarchy -- 5 Other Classes -- 6 Summary of Facts and Open Questions -- References
505	8		_a18 Further Reading -- Bibliography -- Bibliography of the Works of Stephen A. Cook -- References
505	8		_a Contributors' Biographies
505	8		_aAuthors' Biographies
505	8		_aIndex
506			_aAbstract freely available; full-text restricted to subscribers or individual document purchasers.
530			_aAlso available in print.
538			_aMode of access: World Wide Web
538			_aSystem requirements: Adobe Acrobat Reader
650		0	_aLogic, Automata, and Computational Complexity(Computer Science)
655		0	_aElectronic books.
776	0	8	_iPrint version: _z9798400707797 _z9798400707773
830		0	_aACM books - Collection 2 ; _v#43.
856	4	0	_3Abstract with links to full text _uhttps://doi.org/10.1145/3588287
999			_c400 _d400