COMPUTATIONAL COMPLEXITY

3 credits.

Study of the capabilities and limitations of efficient computation. Relationships between models representing capabilities such as parallelism, randomness, quantum effects, and non-uniformity; and models based on the notions of nondeterminism, alternation, and counting, which capture the complexity of important problems. Knowledge of the theory of computation is strongly encouraged, such as COMP SCI 520 .