Computational and Complexity Theory

This course gives a basic idea about various languages such as decidable, undecidable, recursive, and recursively enumerable languages. Decidable language and its examples are explained. The differences between the languages are mentioned. It discusses problems and theorems based on the languages specified. A famous theorem called the Rice theorem is discussed along with its main property called Non-Trivial Property. A non-trivial property is a very important one in order to state the rice theorem. In the explanation of the Rice theorem, two theorems are discussed and explained in a detailed manner. Few quizzes and question and answer sections are given to improve the knowledge on the same. A problem called Post correspondence problem which is undecidable that is explained in a detailed way. The modified version of the Post correspondence problem is called MPCP which is also discussed in this course. The conversion of MPCP to PCP is explained. The step-by-step conversion with an example is explained in the lecture. How the Post Correspondence Problem is called Undecidable is also discussed. The closure properties and their relations are discussed. At last, classes under complexity theory such as P, NP, NP-Hard, and NP-Complete are clearly explained. The differences between the classes are elaborated in an understandable way.