Formal Languages and Computability (INF3, Autumn'05)
Lecture 13
Main topic:
Introduction to time complexity
Lecture Plan
- measuring complexity of Turing machines
- big-O and small-o notation
- polynomial robustness of variants of Turing machines
- complexity of nondeterministic Turing machines
- complexity class P, closure properties and examples of problems in P
Reading
- Section 7.1 (251-260)
- Section 7.2 (260-264)