134     0      0      0

Computational Complexity  

Sudebkumar Prasant Pal
CS41103 Autumn 2021-22
IIT Kharagpur

 

OVERVIEW 

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.



SIMILAR RESOURCES 

Computational Complexity (6)
 

DISCUSSIONS 


 


 
 

USEFUL DOCUMENTS

Documents uploaded to this collection

No document has been added by the curator to this collection yet.

 

Curated By

Sudebkumar Prasant Pal  

IIT Kharagpur

...

 View Profile


Contributors and Coauthors

Contributors to this collection

 

Workshops and Short Courses  

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

Books relevant to this collection

 
 

DOCUMENTS

Documents uploaded to this collection

No document has been added by the curator to this collection yet.

 

PAPERS

Journal papers etc relevant to this collection

No journal paper, dissertation or book chapter has been added by the curator to this collection yet.

 

Questionbank

No questions have been added to the question bank yet.

BOOKS

Books relevant to this collection

 
 

VIDEOS

All videos in this lecture series

 

PATENTS

Patents added to this collection

No patent document has been added by the curator to this collection yet.

 

EXTERNAL RESOURCES

Webresorces for this collection

    CMSC 652 --- Complexity Theory...