We're still actively developing this site. If you encounter any issues, please report them! - Report an issue

COMPUTATIONAL COMPLEXITY

COMPSCI 710
Course Description

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 asCOMP SCI 520.

Prerequisites

Graduate/professional standing

Satisfies

This course does not satisfy any prerequisites.

Credits

Not Reported

Offered

Not Reported

Grade Point Average
3.14

-12.58% from Historical

Completion Rate
96.43%

-2.6% from Historical

A Rate
21.43%

-61.04% from Historical

Class Size
28

96% from Historical

Cumulative Grade Distribution

Instructors (2026 Summr)

Sorted by ratings from Rate My Professors

Similar Courses

INTRODUCTION TO ALGORITHMS

COMPSCI 577

Basic paradigms for the design and analysis of efficient algorithms: greed, divide-and-conquer, dynamic programming, reductions, and the use of randomness. Computational intractability including typical NP-complete problems and ways to deal with them.

INTRODUCTION TO THEORY OF COMPUTING

COMPSCI 520

Basics about the notion, capabilities, and limitations of computation: elements of finite automata and regular languages, computability theory, and computational complexity theory. Additional topics include context-free grammars and languages, and complexity-theoretic cryptography.

TOPICS IN THEORETICAL COMPUTER SCIENCE

COMPSCI 880

Advanced topics in algorithms, complexity, and cryptography. The exact topic varies.

COMPUTABILITY THEORY

MATH 773

Turing degree and jump, strong reducibilities, arithmetic hierarchy, index sets, simple and (hyper)hypersimple sets, easy forcing arguments in computability theory, finite and infinite injury, Friedberg-Muchnik and Sacks Splitting Theorem, Sacks Jump and Sacks Density Theorems, computable ordinals. Familiarity with the topics in a basic Foundations course such asMATH 770is strongly recommended.

ADVANCED ALGORITHMS

COMPSCI 787

Advanced paradigms for the design and analysis of efficient algorithms, including the use of randomness, linear programming, and semi-definite programming. Applications to data structures, approximating NP-hard optimization problems, learning, on-line and distributed problems. Students are strongly encouraged to have introductory knowledge of algorithms (e.g.,COMP SCI 577)