CS 278. Machine-Based Complexity Theory

Catalog Description: Properties of abstract complexity measures; Determinism vs. nondeterminism; time vs. space; complexity hierarchies; aspects of the P-NP question; relative power of various abstract machines.

Units: 3.0

Prerequisites: 170.

Fall: 3 hours of lecture per week
Spring: 3 hours of lecture per week

Grading basis: letter

Final exam status: No final exam

Class Schedule (Spring 2021):
TuTh 2:00PM - 3:29PM, Internet/Online – Avishay Tal, PhD

Class homepage on inst.eecs

Related Areas: