The complexity of theorem-proving procedures
Article
Domain Context
Computation and Complexity
Citation
Stephen A. Cook. (1971). The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158.
Why this reference is included
Cook’s 1971 The complexity of theorem-proving procedures, published in Proceedings of the Third Annual ACM Symposium on Theory of Computing, is one of the program’s working technical references. Cited in Book III (Categorical Spectrum), Part 9, Chapter The τ-Tower Machine, where the program draws on it in the context of “Constant-width Cook–Levin tableau. In the classical Cook–Levin theorem , a Turing machine computation on input of length n is encoded as a Boolean tableau with T(n) rows (one per….”
Cited in
-
Book III — Categorical Spectrum Part 9Chapter The τ-Tower Machine
Constant-width Cook–Levin tableau. In the classical Cook–Levin theorem , a Turing machine computation on input of length n is encoded as a Boolean tableau with T(n) rows (one per time step) and S(n) columns (one per tape cell)