Logic, Automata, and Computational Complexity/ The Works of Stephen A. Cook Bruce M. Kapron.

Format:

Book

Author/Creator:

Kapron, Bruce M., editor.

Series:

ACM books - Collection 2 ; #43.

ACM books, 2374-6777 ; #43

Language:

English

Subjects (All):

Logic, Automata, and Computational Complexity(Computer Science).

Genre:

Electronic books.

Physical Description:

1 online resource (xxvi, 399pages) LuaTEX

Edition:

First Edition

Place of Publication:

[New York, NY, USA] : Association for Computing Machinery; [2023].

System Details:

Mode of access: World Wide Web

System requirements: Adobe Acrobat Reader

Contents:

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

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

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

10 Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

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

11 The Relative Efficiency of Propositional Proof Systems

2 Frege Systems

3 Natural Deduction Systems

4 Extended Frege Systems

5 The Substitution Rule

12 Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version)

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

13 Towards a Complexity Theory of Synchronous Parallel Computation

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

14 A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation

Key words

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

15 Pebbles and Branching Programs for Tree Evaluation

2 Preliminaries

3 Connecting TMS, BPS, and Pebbling

4 Pebbling Bounds

5 Branching Program Bounds

6 Conclusion

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

18 Further Reading

Bibliography

Bibliography of the Works of Stephen A. Cook

Contributors' Biographies

Authors' Biographies

Index

Other Format:

Print version:

ISBN:

3588287

9798400707803

9798400707780

Access Restriction:

Restricted for use by site license.