Computational Complexity

4 credits · College of Engineering catalogue

Advisory Prerequisite: Coursework in probability and algorithms. Enforced Prerequisite: EECS 376 ; No OP/F; or graduate standing. Minimum grade requirement of “B+” for enforced prerequisite. (4 credits) Fundamentals of the theory of computation and complexity theory. Computability, undecidability, and logic. Relations between complexity classes, NP-completeness, P-completeness, and randomized computation. Applications in selected areas such as cryptography, logic programming, theorem proving, approximation of optimization problems, or parallel computing.