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.
