CS 579

Fall 2026 All Classes

All Classes

Computational Complexity

Credit: 4 hours.

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.

Same as ECE 579. Prerequisite: One of CS 473, CSE 414, MATH 473, CS 475 or MATH 475.

My Favorites

My Schedule

Section Status updates every 10 minutes.

CS 579 class schedule data for fall 2026
	Status		CRN	Type	Section	Time	Day	Location	Instructor	Section Details
			51780	Lecture-Discussion	F	3:30PM -4:45PM	TR	1302 Siebel Center for Comp Sci	Forbes, M	Availability: CrossListOpen (Restricted) Part of Term: 1 Date Range: 08/24/26-12/09/26 Credit: 4 hours Section Info: For up-to-date information about CS course restrictions, please see the following link: http://go.cs.illinois.edu/csregister Restriction(s): Restricted to Computer Science or Bioinformatics major(s). Restricted to Graduate - Urbana-Champaign. Not intended for MCS: Computer Sci OFF - UIUC, MCS:Computer Sci Online -UIUC, or NDEG:Computer Science Onl-UIUC. Not intended for First Time Freshman students.