Bulletin Year: 2022 - 2023 Graduate Bulletin | View the current NMU Catalog.
CS 520 Computational Complexity Theory 4 cr.  (4-0-0)

This course is an introduction to computational complexity theory and standard complexity classes. Prior knowledge of discrete mathematics and algorithms is assumed. By investigating the amount of resources (like time, memory …) to solve computational problems, we classify them into different complexity classes and explore the relationship between these classes. Topics include deterministic and nondeterministic Turing machines, diagonalization, decidable and undecidable languages, DTIME and NTIME complexity classes, P, NP and coNP classes, polynomial-time reductions, NP-hard and NP-complete problems, space complexity, polynomial hierarchy, Boolean circuits, non-uniform complexity, and randomized computation.