Sign In

 CSE 613: Computational Complexity

​Course Information

Designation:   Required Course

Course Level:   Graduate


Prerequisite(s) by Topic: 

ICS 552 or Consent of the Instructor

Catalog Description: 

Computational complexity. Time-space complexities. Speedup, hierarchy theorems. Time-Space Tradeoff. Translational Lemmas. Gap and Union theorems. Intractable problems – polynomial time space. Theory of NP-Completeness – Classes, P, NP, Co-NP, PSPACE. Poly-Time and Log-Space transformations. Proof techniques for establishing NP-Completeness. Turing Reducibilities and polynomial hierarchy. Using NP-Completeness to Analyze problems. NP-Hardness. Introduction to Approximation algorithms to hard problems.​