ECE 579
Computational Complexity

Displaying course information from Spring 2014.

Section Type Times Days Location Instructor
F LCD 1100 - 1215 T R   1131 Siebel Center for Comp Sci  Mahesh Viswanathan
Official Description Course Information: Same as CS 579. See CS 579.
Subject Area General Sciences
Course Prerequisites Credit in CS 473 or CS 475
Course Directors Michael C Loui
Detailed Description and Outline

Topics:

  • Turing machines, nondeterminism, hierarchy and simulation theorems
  • Deterministic and nondeterministic sequential classes
  • Random sequential classes
  • Alternation, polynomial-time hierarchy
  • Circuit complexity, parallel complexity
  • Relativized computational complexity
  • Time-space trade-offs
  • Review

Same as CS 579 and MATH 579.

Texts
D.-Z. Du and K.-I. Ko, Theory of Computational Complexity, Wiley, 2000.
Current literature.
Last updated: 2/13/2013