CS 579

Fall 2025 Part of Term 1

Part of Term 1
Aug 25-Dec 10

Computational Complexity

SHOW FINAL EXAM SCHEDULE

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 2025
	CRN	Type	Section	Time	Day	Location	Instructor	Section Details
	51780	Lecture-Discussion	F	3:30PM -4:45PM	TR	1302 Siebel Center for Comp Sci	Granha Jeronimo, F	Part of Term: 1 Date Range: 08/25/25-12/10/25 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 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.