Computational Complexity II
Download as PDF
Course Description
A continuation of CS254 (Computational Complexity). Topics include Barriers to P versus NP; The relationship between time and space, and time-space tradeoffs for SAT; The hardness versus randomness paradigm; Average-case complexity; Fine-grained complexity; Current and new areas of complexity theory research. Prerequisite: CS254.
Grading Basis
ROP - Letter or Credit/No Credit
Min
3
Max
3
Course Repeatable for Degree Credit?
No
Course Component
Discussion
Enrollment Optional?
Yes
Course Component
Lecture
Enrollment Optional?
No
Does this course satisfy the University Language Requirement?
No
Programs
CS254B
is a
completion requirement
for:
- (from the following course set: )
- (from the following course set: )
- (from the following course set: )