skip to main content

CS 579 - Computational Complexity

Spring 2020

TitleRubricSectionCRNTypeHoursTimesDaysLocationInstructor
Computational ComplexityCS579F41446LCD1530 - 1645 T R  1109 Siebel Center for Comp Sci Michael A Forbes
Computational ComplexityECE579F41445LCD1530 - 1645 T R  1109 Siebel Center for Comp Sci Michael A Forbes

Official Description

Turing machines; determinism and non-determinism; time and space hierarchy theorems; speed-up and tape compression; Blum axioms; structure of complexity classes NP, P, NL, L, and PSPACE; complete problems; randomness and complexity classes RP, RL, and BPP; alternation, polynomial-time hierarchy; circuit complexity, parallel complexity, NC, and RNC; relativized computational complexity; time-space trade-offs. Course Information: Same as ECE 579. Prerequisite: CS 473 or CS 475.