Abstract: The fundamental question of computational complexity theory is how much of some computational resource, e.g., time or space, is needed to test if a given input has a certain property. Mathematical logic offers a series of formalisms to precisely express such properties. One might expect that some properties that are complex to compute would be difficult to express. Unexpectedly, the computational complexity of a property can be completely and elegantly understood via the richness of the logical language needed to express it.

This logical approach, called descriptive complexity, has not only achieved elegant characterizations of all important complexity classes but it has led to some major advances in complexity theory. In this talk I will survey the relationships, the advances, and the current challenges of the logical approach to complexity.

Bio: Neil Immerman is the winner, jointly with Róbert Szelepcsényi, of the 1995 Gödel Prize in theoretical computer science. Immerman is one of the key developers of an active research program called descriptive complexity, an approach he is currently applying to research in model checking, database theory, and computational complexity theory. Immerman is an editor of Information and Computation and the Chicago Journal of Theoretical Computer Science. He received B.S. and M.S. degrees from Yale University in 1974 and his Ph.D. from Cornell University in 1980. His book Descriptive Complexity appeared in 1999.