Abstract:

What is Computational Complexity Theory? What is the P vs. NP problem?

Computational Complexity Theory is the mathematical theory that deals with the quantitative study of the nature of efficient computation. Here being efficient means that the number of steps in the computation is polynomially bounded on a problem of size n. Such problems form the class P. NP consists of problems which can be solved efficiently if one can have clever guesses. It is a major open problem in Theoretical Computer Science (and in Mathematics) whether P = NP.

While the primary objects we study in this field are complexity classes, such as P and NP, the field is full of, and greatly motivated by, very concrete computational problems. In fact, many different areas of mathematics inform and interact with this field, including recursion theory, graph theory, number theory, algebraic combinatorics such as designs and codings, operations research, and probability.

In this talk I will try to give a historical overview of the field and some of its central problems and concepts. These include questions such as determinism vs non-determinism; time vs space; proof and verification; and the role of randomization. We will emphasize concrete problems rather than abstract theory. No prior knowledge of the subject is assumed.