CS 312 - Logic, Computability, and Complexity

(4)

FA, alternate years. An introduction to first-order logic, computability and computational complexity. Topics covered include soundness and completeness of a formal proof system, computability and non-computability, and computational complexity with an emphasis on NP-completeness. Crosslisted as MATH 312. Prerequisite(s): MATH 255; or MATH 251 and MATH 252.