CSC 684 Complexity of Computation (5845) (3 credits)

P and NP problems; NP-complete classes; concrete complexity and the P class of combinatorial problems; complexity reduction on graph and string problems; complexity of algebraic computations

Prerequisite: CSC 551 Design and Analysis of Algorithms, CSC 554 Theory of Computation.