Computer Science
CS 4805: Fundamentals of Complexity Theory
Lecture - 4 credits
ND
EI
IC
FQ
SI
AD
DD
ER
WF
WD
WI
EX
CE
- 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.
Reviews basic material such as automata, Turing machines, (un)decidability, time complexity, P vs. Show more.
Pre-requisites