THEORY OF COMPUTATION Anna University Coimbatore Syllabus

THEORY OF COMPUTATION


UNIT I Church-Turing thesis: Turing machines – Variants of Turing Machines – Hilbert’s problems. Decidability: Decidable languages – Halting problem.

UNIT II 9

Reducibility: Undecidable problems from Language theory – A simple Undecidable problem – Mapping Reducibility. Advanced topics in Computability Theory: The Recursion Theorem – Decidability of logical theories – Turing Reducibility.

UNIT III

Time Complexity: Measuring Complexity – The Class P – The class NP – NPcompleteness – Additional NP-complete Problems.

UNIT IV 9
Space Complexity: Savitch’s Theorem – The Class PSPACE – PSPACE-completeness – The classes L and NL – NL-completeness – NL equals coNL. Intractability: Hierarchy Theorems – Relativization – CircuitComplexity.

UNIT V

Advanced topics in complexity theory: Approximation Algorithms – Probabilistic Algorithms – Alternation – Interactive Proof Systems – Parallel Computation – Cryptography


TEXT BOOKS:
1. Michael Sipser, Introduction to the Theory of Computation, Thomson Brook/cole, 1997.(2006)
2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, 3/E, Pearson Education, 2009.
REFERENCES
1. Peter Linz, An Introduction to formal Languages and Automata, 4/ E, Jones & Bartlett Pub, 2006.
2 Kamala Krithivasan, Rama R, Introduction to Formal Languages, Automata Theory and Computation, Pearson, 2009
3. Dr. B. N. Srinivasa Murthy, Formal Languages and Automata Theory, Sanguine Publishers, 2006.