Introduction to Computational Complexity. 3 credits, 3 contact hours

Catalog description

Prerequisites: CS 610 or CS 435 , or doctoral student status. While efficient algorithms have been discovered for many computational problems, many other problems appear to be computationally hard. Such problems appear in disparate contexts and they often look quite different. Computational Complexity is the systematic study of computationally hard problems that uncovers hidden relationships among them. This course introduces the fundamentals of Computational Complexity and provides an understanding of both the inherent capabilities and limitations of computation. Topics include: Computability, Reductions, NP-Completeness and Time Complexity, Space Complexity, Computational Hierarchies, Parameterized and Fine-Grained Complexity, Interactive Proofs, Complexity of Counting, and Basic Cryptography.