Lecture 12: Time Complexity

Om kurset

Description: Quickly reviewed last lecture. Gave an introduction to complexity theory. Discussed limited complexity model-dependence for reasonable models. Defined TIME\((t(n))\) complexity classes and the class P. Showed that \(PATH\) ∈ P. Instructor: Prof. Michael Sipser