A card from a free library — ask anything, no account, works offline. Every card carries its source.
S. A. Cook 1971 — The complexity of theorem-proving procedures
source
S. A. Cook (1971). The complexity of theorem-proving procedures. Proc. 3rd ACM STOC (1971) 151–158. DOI 10.1145/800157.805047. Canonical: https://doi.org/10.1145/800157.805047. Free copy: https://www.cs.umd.edu/~gasarch/COURSES/452/F14/cookpaper.pdf. License as found: ACM copyright policy (acm.org/publications/policies/copyright_policy) — publisher's copyright, cited. Serves the P versus NP stick (stick_p_versus_np): SAT is NP-complete — the completeness link the ladder stands on — fills the want want_54d4b9cd0f1a.
source
card id
card_src_mill_cook_1971
address
SCI.millennium.FCT/the-complexity-of-theorem-proving-procedures/REF.WITNESSED@s-a-cook
adjoining cards
- on the shelf of → The Millennium sources — the papers behind the seven sticks — a source the P versus NP stick (stick_p_versus_np) cites, located for a want and carded by
- builds on → Hartmanis 1965 — On the computational complexity of algorithms — a later work standing on an earlier one
- builds on → Cobham 1965 — The intrinsic computational difficulty of functions — a later work standing on an earlier one
- builds on → Shannon 1949 — The synthesis of two-terminal switching circuits — a later work standing on an earlier one
- enables → R. M. Karp 1972 — Reducibility among combinatorial problems — a later work standing on an earlier one
- enables → Baker 1975 — Relativizations of the P =? NP question — the first barrier: no relativizing proof can settle the question
Is this card incomplete? Tell the library — it will call out for more ↗