Logic, Automata, and Computational Complexity/ The Works of Stephen A. Cook
Kapron, Bruce M.
Logic, Automata, and Computational Complexity/ The Works of Stephen A. Cook Bruce M. Kapron. - First Edition - 1 PDF (xxvi, 399pages) LuaTEX - ACM books, #43 2374-6777 ; . - ACM books - Collection 2 ; #43. .
Introduction -- Acknowledgments PART 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 PART II THE TURING AWARD LECTURE 3 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 PART 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 PART 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 -- 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 -- 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 -- Acknowledgment -- 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 -- 2 Preliminaries -- 3 Connecting TMS, BPS, and Pebbling -- 4 Pebbling Bounds -- 5 Branching Program Bounds -- 6 Conclusion -- Acknowledgments -- References PART V THE BERKELEY NOTES 16 Cook's Berkeley Notes 17 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 18 Further Reading -- Bibliography -- Bibliography of the Works of Stephen A. Cook -- References Contributors' Biographies Authors' Biographies Index
Abstract freely available; full-text restricted to subscribers or individual document purchasers.
Mode of access: World Wide Web
System requirements: Adobe Acrobat Reader
3588287 9798400707803 9798400707780
10.1145/3588287 doi
Logic, Automata, and Computational Complexity(Computer Science)
Electronic books.
Logic, Automata, and Computational Complexity/ The Works of Stephen A. Cook Bruce M. Kapron. - First Edition - 1 PDF (xxvi, 399pages) LuaTEX - ACM books, #43 2374-6777 ; . - ACM books - Collection 2 ; #43. .
Introduction -- Acknowledgments PART 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 PART II THE TURING AWARD LECTURE 3 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 PART 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 PART 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 -- 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 -- 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 -- Acknowledgment -- 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 -- 2 Preliminaries -- 3 Connecting TMS, BPS, and Pebbling -- 4 Pebbling Bounds -- 5 Branching Program Bounds -- 6 Conclusion -- Acknowledgments -- References PART V THE BERKELEY NOTES 16 Cook's Berkeley Notes 17 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 18 Further Reading -- Bibliography -- Bibliography of the Works of Stephen A. Cook -- References Contributors' Biographies Authors' Biographies Index
Abstract freely available; full-text restricted to subscribers or individual document purchasers.
Mode of access: World Wide Web
System requirements: Adobe Acrobat Reader
3588287 9798400707803 9798400707780
10.1145/3588287 doi
Logic, Automata, and Computational Complexity(Computer Science)
Electronic books.