MATH-312   Logic, Computability and Complexity

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. Also listed as computer science 312. Prerequisite: Mathematics 256.