The Complexity of Theorem-Proving Procedures ​

← Back to topic

Authors: Stephen A. Cook
Year: 1971
Journal: STOC
DOI: 10.1145/800157.805047
Publisher: https://dl.acm.org/doi/10.1145/800157.805047

Keywords: cook theorem, np completeness

Abstract ​

We show that the class NP is as easy to recognize as it is to solve.

Cite this paper ​

@misc{cookstoc1971,
  title  = {The Complexity of Theorem-Proving Procedures},
  author = {Stephen A. Cook},
  year   = {1971},
  journal = {STOC},
  doi    = {10.1145/800157.805047},
  url    = {https://doi.org/10.1145/800157.805047},
}

Source files ​

• metadata.json
• paper.bib