Course Websites

ECE 579 - Computational Complexity

Last offered Fall 2023

Official Description

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

Related Faculty

Subject Area

  • Computer Engineering

Course Director

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.
TitleSectionCRNTypeHoursTimesDaysLocationInstructor
Computational ComplexityF51781LCD41530 - 1645 T R  1302 Siebel Center for Comp Sci Michael A Forbes