CS41103: Computational Complexity

CS41103
Course name	Computational Complexity
Offered by	Computer Science & Engineering
Credits	4
L-T-P	3-1-0
Previous Year Grade Distribution
{{{grades}}}
Semester	Autumn

Syllabus

Syllabus mentioned in ERP

Computational Models (machine models, logic); Problems, computability, Algorithms, Resources, and Complexity; Turing machines (time and space bounds, nondeterminism); Logic (Boolean logic, circuits, first and second order logic); Complexity classes (hierarchy theorem, reachability, P, NP, Co-NP); Reduction and completeness; Randomized computation; Approximability; Cryptography and protocols; Parallel Computation; Polynomial Hierarchy; Logarithmic space; Polynomial space; Exponential time and space.References1.Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Longman.2.Michael Sipser, Introduction to the Theory of Computation, PWS Publishing.3.John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata, Languages and Computation, Addison-Wesley, 1979.4.J. Balcazar, J. Diaz, and J. Gabarro, Structural Complexity, Volumes I and II, Springer.