Computational Complexity

Description from DukeHub

Turing machines, undecidability, recursive function theory, complexity measures, reduction and completeness, NP, NP-Completeness, co-NP, beyond NP, relativized complexity, circuit complexity, alternation, polynomial time hierarchy, parallel and randomized computation, algebraic methods in complexity theory, communication complexity. Prerequisite: Computer Science 334 or equivalent.

Skills

• programmingdepartment: COMPSCI

AI-resilient: 0 of 5 0/5

• No: Physical, lab or field work
• No: Live work with people
• No: Judgment someone is accountable for
• No: A craft you practice with your hands or body
• No: Small, in-person format

The checks lean on Microsoft Research, Working with AI (2025), which found generative AI applies least to physical work and hands-on work with people. A signal, not a promise. How the score works

More in COMPSCI

• Introduction to Computer Science COMPSCI 101L
• Data Structures and Algorithms COMPSCI 201
• Introduction to Computer Systems COMPSCI 210D
• Everything Data COMPSCI 216
• Discrete Math for Computer Science COMPSCI 230
• Computer Architecture COMPSCI 250D

All COMPSCI courses · All of Graduate School