ECE 579

spring 2005
 
All Classes
Computational Complexity

Credit: 4 hours.

(ECE 479) 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, PSPACE; complete problems; randomness and complexity classes RP, RL, BPP; alternation, polynomial-time hierarchy; circuit complexity, parallel complexity, NC, RNC; relativized computational complexity; time-space trade-offs. Same as CS 579 and MATH 578. Prerequisite: CS 473 or CS 475 or consent of instructor

Closed
Section Status Closed
Open
Section Status Open
Pending
Section Status Pending
Open (Restricted)
Section Status Open (Restricted)
Unknown
Section Status Unknown
Section Status updates every 10 minutes.
Detail Status CRN Type Section Time Day Location Instructor