| |
Apr 24, 2024
|
|
|
|
|
CS 6060 - Computational Complexity
Complexity of computational problems explored with respect to a variety of complexity measures. Topics iinclude deterministic time complexity, nondeterministic time complexity, the polynomial-time hierarchy, average-case time complexity, space-bounded complexity, circuit complexity, reductions, relativizations, and parallel models of computation.
Requisites: CS 5060
Credit Hours: 3
Repeat/Retake Information: May not be retaken.
Lecture/Lab Hours: 3.0 lecture
Grades: Eligible Grades: A-F,WP,WF,WN,FN,AU,I
Learning Outcomes:
- Students will be able to place problems within their appropriate complexity classes.
- Students will gain an understanding of structural complexity, well-known complexity classes, and reduction techniques.
- Students will gain an understanding of the known relationships among complexity classes.
- Students will understand and be able to employ proof techniques related to computational complexity.
- Students will understand oralcle relativization results and their implications in structural complexity.
Add to Portfolio (opens a new window)
|
|
