Here is an accessible, algorithmically oriented guide to some of the most interesting techniques of complexity theory. The book shows that simple algorithms are at the heart of complexity theory. The book is organized by technique rather than by topic. Each chapter focuses on one technique: what it is, and what results and applications it yields.

About - Computational Complexity

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.