Logic, Automata, and Computational Complexity/ (Record no. 400)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 05943nam a2200661 i 4500 |
| 001 - CONTROL NUMBER | |
| control field | 9798400707803 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | ACM |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20260528133339.0 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 230523s2023 nyu 001 0deng d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 3588287 |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9798400707803 |
| Qualifying information | ebook |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9798400707780 |
| Qualifying information | epub |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Canceled/invalid ISBN | 9798400707797 |
| Qualifying information | hardcover |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Canceled/invalid ISBN | 9798400707773 |
| Qualifying information | paperback |
| 024 7# - OTHER STANDARD IDENTIFIER | |
| Standard number or code | 10.1145/3588287 |
| Source of number or code | doi |
| 100 0# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Kapron, Bruce M. |
| Relator term | editor. |
| 245 10 - TITLE STATEMENT | |
| Title | Logic, Automata, and Computational Complexity/ |
| Remainder of title | The Works of Stephen A. Cook |
| Statement of responsibility, etc. | Bruce M. Kapron. |
| 250 ## - EDITION STATEMENT | |
| Edition statement | First Edition |
| 264 #1 - PRODUCTION, PUBLICATION, DISTRIBUTION, MANUFACTURE, AND COPYRIGHT NOTICE | |
| Place of production, publication, distribution, manufacture | [New York, NY, USA] : |
| Name of producer, publisher, distributor, manufacturer | Association for Computing Machinery; |
| Date of production, publication, distribution, manufacture, or copyright notice | [2023]. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | 1 PDF (xxvi, 399pages) |
| Other physical details | LuaTEX |
| 490 1# - SERIES STATEMENT | |
| Series statement | ACM books, |
| International Standard Serial Number | 2374-6777 ; |
| Volume/sequential designation | #43 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Introduction -- Acknowledgments |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | PART I BIOGRAPHICAL BACKGROUND |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 2 ACM Interview of Stephen A. Cook by Bruce M. Kapron |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | PART II THE TURING AWARD LECTURE |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | PART III PERSPECTIVES ON COOK'S WORK |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 8 Computation with Limited Space -- 8.1 Time and Space Bounds -- 8.2 Pebbling -- 8.3 Circuits -- 8.4 Branching Programs |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | PART IV SELECTED PAPERS |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 9 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# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | PART V THE BERKELEY NOTES |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 16 Cook's Berkeley Notes |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 18 Further Reading -- Bibliography -- Bibliography of the Works of Stephen A. Cook -- References |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Contributors' Biographies |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Authors' Biographies |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Index |
| 506 ## - RESTRICTIONS ON ACCESS NOTE | |
| Terms governing access | Abstract freely available; full-text restricted to subscribers or individual document purchasers. |
| 530 ## - ADDITIONAL PHYSICAL FORM AVAILABLE NOTE | |
| Additional physical form available note | Also available in print. |
| 538 ## - SYSTEM DETAILS NOTE | |
| System details note | Mode of access: World Wide Web |
| 538 ## - SYSTEM DETAILS NOTE | |
| System details note | System requirements: Adobe Acrobat Reader |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name entry element | Logic, Automata, and Computational Complexity(Computer Science) |
| 655 #0 - INDEX TERM--GENRE/FORM | |
| Genre/form data or focus term | Electronic books. |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
| Relationship information | Print version: |
| International Standard Book Number | 9798400707797 |
| -- | 9798400707773 |
| 830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE | |
| Uniform title | ACM books - Collection 2 ; |
| Volume/sequential designation | #43. |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Materials specified | Abstract with links to full text |
| Uniform Resource Identifier | <a href="https://doi.org/10.1145/3588287">https://doi.org/10.1145/3588287</a> |
No items available.