3 credits (3-0-0)
Pre-requisites: COL352 OR Equivalent
Review of Automata Theory, Turing Machines and Universal Turing Machines. Computability & Undecidability, Rice’s theorem. Computational Complexity: Time and Space hierarchy, Gap theorem, Classes P and NP, Cook-Levin theorem, PSPACE completeness, NL completeness, Immerman-Szelepcseyi theorem, Alternation, Polynomial hierarchy, Permanent and #P completeness, Oracle machines, Baker-Gill-Solovay theorem, Randomized Turing Machine, RP, ZPP, BPP, Adleman’s theorem, Yao’s minmax theorem, Derandomization.