Detailed Course Information |
Spring 2024 Semester
May 14, 2024 |
|
 |
||
 | Select the desired Level or Schedule Type to find available classes for the course. |
| CS 4805 - Fundamentals of Complexity Theory |
|
Reviews basic material such as automata, Turing machines, (un)decidability, time complexity, P vs. NP, and NP-completeness. Studies core topics in computational complexity, including time and space complexity, polynomial hierarchy, circuit complexity, probabilistic computation, interactive proofs, and hardness of approximation. Optional topics may include Gödel's incompleteness theorem, Kolgomorov complexity, cryptography, quantum computing, communication complexity, lower bounds, or pseudorandomness.
4.000 Credit hours 4.000 Lecture hours Levels: Undergraduate Schedule Types: Lecture Computer Science Department Course Attributes: Computer&Info Sci Restrictions: Must be enrolled in one of the following Levels: Undergraduate Prerequisites: Undergraduate level CS 3800 Minimum Grade of D- |
| Return to Previous | New Search |
|