NP-complete problems: Samuel’s tutorial

Summary: Samuel's tutorial on NP-complete problems.
Topics: P versus NP, decision problems, verification algorithms, NP-completeness
Slides: link (pdf)

  • A. Turing, "On computable numbers, with an application to the Entscheidungsproblem", J. of Mathematics (1936)
  • C. Strachey, "An impossible program", The Computer Journal (1965)
  • A. Cobham, "The intrinsic computational difficulty of functions", (1965)
  • S. Cook, "The complexity of theorem-proving procedures", ACM symposium on Theory of Computing (1971)
  • R. Karp, "Reducibility among combinatorial problems", Complexity of Computer Computations (1972)
  • C. Petzold, "The annotated Turing: a guided tour through Alan Turing's historic paper on computability and the Turing machine" (2008)
  • J. Erickson, (2016)
  • D. Wilmer, Graduate Algorithms, Lecture 36, (2017)
  • J. Erickson, Algorithms, (2019)
  • T. Cormen et al., "Introduction to algorithms", Chap 34, MIT press (2022)