{"id": "card_src_mill_cook_1971", "kind": "reference", "title": "S. A. Cook 1971 — The complexity of theorem-proving procedures", "body": "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": {"label": "S. A. Cook (1971), Proc. 3rd ACM STOC (1971) 151–158", "url": "https://doi.org/10.1145/800157.805047", "domain": "computer_science", "authority_tier": "reference"}, "shelf": "millennium", "box": "source", "bands": ["p_vs_np", "millennium", "source", "paper", "cook", "1971", "p versus np"], "subject": "The complexity of theorem-proving procedures", "connections": [{"to_card_id": "card_spine_millennium_sources", "relationship": "member_of", "evidence": "a source the P versus NP stick (stick_p_versus_np) cites, located for a want and carded by its record"}, {"to_card_id": "card_chain_hartmanis_stearns_1965", "relationship": "builds_on", "evidence": "a later work standing on an earlier one"}, {"to_card_id": "card_chain_cobham_1965", "relationship": "builds_on", "evidence": "a later work standing on an earlier one"}, {"to_card_id": "card_chain_shannon_1949", "relationship": "builds_on", "evidence": "a later work standing on an earlier one"}, {"to_card_id": "card_src_mill_karp_1972", "relationship": "enables", "evidence": "a later work standing on an earlier one"}, {"to_card_id": "card_chain_baker_gill_solovay_1975", "relationship": "enables", "evidence": "the first barrier: no relativizing proof can settle the question"}], "author": "engine", "created_at": 0.0, "updated_at": 0.0, "visibility": "public", "lifecycle_stage": "public", "volatility": "permanent", "surface": "secular", "generated": false, "call": "millennium.s.sa.s_a_cook_1971_the_complexity_of_theorem_proving", "facets": {"subject": ["1971", "cook", "millennium", "p versus np", "p_vs_np", "paper"]}, "presentation": {"glyph": "•", "kind_label": "source", "by": "S. A. Cook (1971), Proc. 3rd ACM STOC (1971) 151–158", "authority": "reference", "posted": "", "standing": "", "link": {"url": "https://doi.org/10.1145/800157.805047", "host": "doi.org", "provider": "", "titled": "S. A. Cook 1971 — The complexity of theorem-proving procedures", "waybill_line": "", "reach": "", "embed": ""}}, "neighbors": [{"id": "card_spine_millennium_sources", "title": "The Millennium sources — the papers behind the seven sticks", "relationship": "on the shelf of", "why": "a source the P versus NP stick (stick_p_versus_np) cites, located for a want and carded by its record", "href": "/card/card_spine_millennium_sources", "resolved": true}, {"id": "card_chain_hartmanis_stearns_1965", "title": "Hartmanis 1965 — On the computational complexity of algorithms", "relationship": "builds on", "why": "a later work standing on an earlier one", "href": "/card/card_chain_hartmanis_stearns_1965", "resolved": true}, {"id": "card_chain_cobham_1965", "title": "Cobham 1965 — The intrinsic computational difficulty of functions", "relationship": "builds on", "why": "a later work standing on an earlier one", "href": "/card/card_chain_cobham_1965", "resolved": true}, {"id": "card_chain_shannon_1949", "title": "Shannon 1949 — The synthesis of two-terminal switching circuits", "relationship": "builds on", "why": "a later work standing on an earlier one", "href": "/card/card_chain_shannon_1949", "resolved": true}, {"id": "card_src_mill_karp_1972", "title": "R. M. Karp 1972 — Reducibility among combinatorial problems", "relationship": "enables", "why": "a later work standing on an earlier one", "href": "/card/card_src_mill_karp_1972", "resolved": true}, {"id": "card_chain_baker_gill_solovay_1975", "title": "Baker 1975 — Relativizations of the P =? NP question", "relationship": "enables", "why": "the first barrier: no relativizing proof can settle the question", "href": "/card/card_chain_baker_gill_solovay_1975", "resolved": true}], "house": {"door": "FIND", "kind": "card", "trail": "connections", "seal": "/card/card_src_mill_cook_1971", "next_step": {"do": "read the source itself", "door": "FIND", "web": "/reader.html?card=card_src_mill_cook_1971"}, "ends": "a verdict or a card · the trail · a seal · one next step"}}