Designation: Required Course
Course Level: Graduate
Prerequisite(s) by Topic:
ICS 552 or Consent of the Instructor
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.