http://cse.iitkgp.ac.in/~spp/cc2021.html CS41103 COMPUTATIONAL COMPLEXITY L-T-P: 3-1-0, Credits: 4 (as in cse website) 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. References ========== Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Longman. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing. John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata, Languages and Computation, Addison-Wesley, 1979. J. Balcazar, J. Diaz, and J. Gabarro, Structural Complexity, Volumes I and II, Springer. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach.
Computational Complexity (6) |
Documents uploaded to this collection
Videos related to this topic
IIT Kharagpur
...
View ProfileContributors to this collection
No short courses scheduled yet
Request a topic of interest.
A short course for this topic has not been currently scheduled. You may request a topic of interst that you would like this instructor to cover in the short course. Please follow this instructor to be notified when any of his or her short courses come online.
Books relevant to this collection
Documents uploaded to this collection
Journal papers etc relevant to this collection
Books relevant to this collection
All videos in this lecture series
Patents added to this collection
 134     0      0      0