CS 579
Fall 2012 Part of Term 1
Part of Term 1
Aug 27-Dec 12
Aug 27-Dec 12
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 and MATH 578. Prerequisite: CS 473 or CS 475.
Section Status updates every 10 minutes.
| CRN | Type | Section | Time | Day | Location | Instructor | Section Details | |
|---|---|---|---|---|---|---|---|---|
|
51780
|
Lecture-Discussion
|
F
|
12:30PM
-1:45PM
|
WF
|
1103 Siebel Center for Comp Sci
|
Kolla, A
|
|