| |
Oct 17, 2026
|
|
|
|
|
2026-2027 University Catalog
|
CS 58400 - Theory Of Computation And Computational Complexity
Credit Hours: 3.00. The theory of general purpose programming systems. Recursive and partial-recursive functions; recursive and recursively enumerable sets. The Church-Turing thesis. The recursion theorem, Rogers’ translation theorem, Rice’s undecidability theorem. The general theory of computational complexity: there are no general solutions to natural optimization problems. Complexity for specific models of computation: the polynomial complexity classes P, NP, and PSPACE; NP-hard and PSPACE-hard problems, inherently exponential problems.
Learning Outcomes
1. Identify classes of problems that are computable by a Turing Machine; the time/space complexity of classical problems and of new problems.
2. Demonstrate ability to write clear and correct mathematical proofs using techniques learnt in the prerequisites (deduction, induction, contradiction) and new specific proof strategies learnt in this class (e.g., diagonalization, computational method).
3. Develop skills to read and understand technical papers in the field (e.g., from conferences such as Computational Complexity, FOCS, STOC, APPROX/RANDOM, ICALP). Critique papers in the field and proof strategies and present them in front of peers. Begin research in theoretical computer science.
Credit Hours: 3.00
|
|