ECE 579 - Computational Complexity

Semesters Offered

Official Description

Course Information: Same as CS 579. See CS 579.

Prerequisites

Credit in CS 473 or CS 475

Subject Area

Computer Engineering

Course Directors

Description

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.

Notes

Same as CS 579 and MATH 579.

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

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