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[edit | edit source]
Syllabus mentioned in ERP[edit | edit source]
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.