— Theory of Computation

Prerequisites & course information

Course Description: Time and space complexity classes. Reductions, completeness, and the role of randomness. Logic and undecidability. Learning Activities: Lecture 3 hour(s), Discussion 1 hour(s). Enrollment Restriction(s): Pass One open to Ph.D. students in Computer Science only and Pass Two open to graduate students in Computer Science only. Grade Mode: Letter. Learning Activities: Lecture 3 hour(s), Discussion 1 hour(s). Enrollment Restriction(s): Pass One open to Ph.D. students in Computer Science only and Pass Two open to graduate students in Computer Science only. Grade Mode: Letter.