Mathematical logic is a broad area encompassing proof theory, computability theory, set theory and model theory. These areas are joined by their focus on the interplay between expressibility, definability and provability. Computational complexity, as part of theoretical computer science, is deeply connected to questions in proof theory and computability theory as well as to related areas including combinatorics and probability. The core goal of computational complexity is to determine the limits of computation; this includes some of the most fundamental open questions in mathematics and theoretical computer science, including the P versus NP question.

### Faculty

##### Sam Buss

Research Areas

Logic and Computational ComplexityComputer Graphics

Computational Complexity