Close Menu

CS 530 - Theory of Computation

Course Description: 

Computability topics such as Turing machines, nondeterministic machines, undecidability, and reducibility. Computational complexity topics such as time complexity, NP-completeness and intractability, time and space hierarchy theorems. Introduces the complexity classes P, NP, NL, L, PSPACE, NC, RNC, BPP and their complete problems.

Credit: 

(3-0-3)

Prerequisite: 

[(CS 430 with min. grade of C)]

Corequisite: 

None