CS 4805 — Fundamentals of Complexity Theory
4 semester hoursUndergraduateLectureOnlineOnline
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.
Prerequisites
- CS 3800 (min D-)
Offering history
| Term | Sections | Enrolled | Capacity | Full | Open seats/section |
|---|---|---|---|---|---|
| Spring 2024 | 1 | 3 | 10 | 30% | 7.0 |
| Fall 2025 | 1 | 1 | 15 | 7% | 14.0 |
Snapshots from scheduled scrapes — not live seat availability. "Full" can exceed 100% when sections over-enroll.
Meeting times
Share of recent sections by weekday: M 0% · T 0% · W 0% · Th 0% · F 0%
Common patterns: async (100% of sections) — in patterns, R means Thursday
Professors
Fall
- Emanuele Viola (100% of students) · reviews
Spring
- Emanuele Viola (100% of students) · reviews
Percentages are each professor's average share of the season's enrolled students in recent terms.
Links
Official catalog (CS course descriptions) · Student reviews on RateMyHusky · All CS courses · Plan it at numap.app