CMSC 452
Elementary Theory of Computation
Techniques are developed to determine the difficulty of a problem relative to a model of computation. Topics include Finite Automata, P, NP, decidability, undecidability, and communication complexity.
Topics
- Finite Automata
- decidability
- undecidability
- and communication complexity
Topics explicitly listed in official catalogue description
Prerequisites & course information
Prerequisite: Minimum grade of C- in CMSC351 ; and permission of CMNS-Computer Science department. Or must be in the (Computer Science (Doctoral), Computer Science (Master's)) program.
Sources
- Course catalogue ↗2026-2027
- Catalogue entry ↗
Catalogue variants
- Elementary Theory of Computation · 3 Credits