Machine-Based Complexity Theory

3 credits · Graduate

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.