CS 579

Fall 2021 All Classes

All Classes

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: CS 473 or CS 475.

My Favorites

My Schedule

Section Status updates every 10 minutes.

CS 579 class schedule data for fall 2021
	CRN	Type	Section	Time	Day	Location	Instructor	Section Details
	51780	Online	F	2:00PM -3:15PM	TR	n.a.	Forbes, M	Part of Term: 1 Date Range: 08/23/21-12/08/21 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 Online -UIUC, MCS:Computer Sci Online -UIUC, or NDEG:Computer Science Onl-UIUC. Not intended for First Time Freshman students.