Keyword Search
Advanced Search
Computer Science and Engineering  Theory of Computation
List Lectures
 First Page [ 1 ]  2  3  4  Last Page
# Lecture Name
Title: Theory of Computation
Department: Computer Science and Engineering
Author: Prof. Somenath Biswas
University: IIT Kanpur
Type: WebLink
The objective of the course is to provide an exposition first to the notion of computability, then to the notion of computational feasibility or tractability.

We first convince ourselves that for our purpose it suffices to consider only language recognition problems instead of general computational problems.

We then provide a thorough account of finite state automata and regular languages, not only because these capture the simplest language class of interest and are useful in many diverse domains.

But also because many fundamental notions like nondeterminism, proofs of impossibility, etc. get discussed at a conceptually very simple level. We then consider context grammars and languages, and their properties.

Next, we consider Turing machines (TMs), show that as a model it is very robust, and the reasonableness of the Church-Turing hypothesis. After we realize TMs can work with (codes of) TMs as inputs, we obtain a universal TM.

We then obtain the separation of the classes r.e., and recursive. A number of TM related problems are shown to be undecidable. Next,Postís correspondence problem (PCP) is shown undecidable.

Finally, we introduce the notion of feasible or tractable computation. Classes NP, co-NP are defined and we discuss why these are important. We discuss the extended Church-Turing hypothesis.

After we discuss polynomial time many-one reducibility and prove Cook-Levin theorem, a number of natural problems from different domains are shown NP-complete.

The treatment is informal but rigorous. Emphasis is on appreciating that the naturalness and the connectedness of all the different notions and the results that we see in the course.
Bodhbridge, Copyright © 2009 All rights reserved., is a portal by BodhBridge ESPL.