UI Wordmark

CS 579 F - Computational Complexity

Campus: Urbana-Champaign


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.

Special Instructions:

For up-to-date information about CS course restrictions, please see the following link: http://go.cs.illinois.edu/csregister

Academic Program Restrictions:

MCS:Computer Sci Online -UIUC

Option 1

Number of Required Visit(s): 0

Course Level: Graduate

Credit: 4

Term(s): Fall


Bachelor's Degree

Master's Degree

Doctoral Degree


Continuing Education

Search Programs

Search Courses


Contact Us

University of Illinois Online
Phone: (866) 633-8465 - Join Us  Facebook
© Copyright 2015 - University of Illinois

Cookie Settings