the open
    research
    Contribute
    Back to the reading lists

    Classic AI: search, logic & planning· 1971

    The complexity of theorem-proving procedures

    Stephen A. Cook (first author) · 1971

    Read the original

    DOI 10.1145/800157.805047OpenAlex W2036265926

    On the reading lists

    Why it matters

    Established NP-completeness, transforming understanding of search and automated reasoning difficulty.

    Condensed from the expert lists' notes.

    The record

    First released
    1971 (from OpenAlex)
    Citations
    7,698 citations, as counted by Semantic Scholar logoSemantic Scholar (non-commercial licence)
    Named by
    the chatgpt list only
    Score
    0.523 · computed rank 212 · consensus 0.41, must-read 0.5, citations percentile 1 (1970s · classic-ai), awards 0, existing lists 0. Method

    Editor's notes

    • Readability check: fail: Cook's NP-completeness result is computer science theory; better learned from a textbook. (AI draft (Claude), not yet reviewed, 2026-10-29)

    Data sources

    Catalogue data from OpenAlex (CC0), Crossref (CC0 metadata; no abstracts are shown), arXiv, and Papers With Code (CC BY-SA 4.0), and Semantic Scholar logoSemantic Scholar (used under its non-commercial API licence). Each count names its source. See the method.