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)
References
- 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, http://jeffe.cs.illinois.edu/teaching/algorithms/models/06-turing-machines.pdf (2016)
- D. Wilmer, Graduate Algorithms, Lecture 36, http://www.cs.cmu.edu/afs/cs/academic/class/15750-s17/ScribeNotes/lecture36.pdf (2017)
- J. Erickson, Algorithms, http://jeffe.cs.illinois.edu/teaching/algorithms/ (2019)
- T. Cormen et al., "Introduction to algorithms", Chap 34, MIT press (2022)