Theory of Computation: Complexity of Problems

This lecture covers the theory of computation, the concept of infinity, undecidable problems, and the theory of complexity. It explains how to measure the complexity of problems in terms of time and space, and the hierarchy of complexity classes. The instructor discusses practical algorithms for search, sorting, and shortest path, emphasizing the importance of efficient algorithms for various computational tasks. The lecture introduces the complexity class P, which represents problems solvable in polynomial time, and provides examples of problems falling into this class. It concludes with a summary of problem classification, distinguishing between undecidable and decidable problems.