Neil Immerman

Rutgers University - Busch Campus
CoRE Building, 1st Floor Lecture Hall
Piscataway, New Jersey
Monday, October 2, 1995
11:00 AM

Title of Discussion



Computational complexity was originally defined in terms of the natural entities of time and space, and the term complexity was used to denote the time or space used in the computation. Yet to a mathematician rather than checking whether an input satisfies a property S, a more natural question might be what is the complexity of expressing the property S? These two issues -- checking and expressing -- are closely related. It is startling how closely tied they are when the latter refers to expressing the property in first-order logic of finite and ordered structures.

We will explain some of the tight relationships between describing versus computing. For example, NP equals the set of second-order existential properties; P equals the set of properties describable in first-order logic plus inductive definitions; and, for all k, DSPACE[n^k] is equal to the set of properties describable by a uniform sequence of first-order sentences using k+1 variables.

Computational complexity has traditionally considered only static problems. Classical Complexity Classes such as NC, P, and NP are defined in terms of the complexity of checking whether the input satisfies a certain property. For many applications a more appropriate complexity measure involves modeling the process as a dynamic one: there is a fairly large object being worked on over a period of time. The object is repeatedly modified by users and computations are performed. In the second part of the talk, we show how the descriptive approach lends itself to the area of Dynamic Complexity.


Neil Immerman received B.S. and M.S. degrees in mathematics from Yale University in 1974 and a Ph.D. degree from Cornell University in 1980. He taught in the computer science departments at Tufts University and Yale University before joining in 1989 the University of Massachusets, Amherst where he is professor of computer science. Dr. Immerman is one of the key developers of the field of descriptive complexity which uses logical expressibility to study computation. He is the winner, jointly with Robert Szelepcsenyi, of the 1995 G"odel Prize in theoretical computer science.

For additional information about the DIMACS special year, please see the following web site:

Prof. Immerman's talk is scheduled in conjunction with the Rutgers Department of Computer Science Special Colloquium Series. For more information about DCS colloquia, please see the following web site:

or contact Sven Dickinson (Colloquium Committee Chair) at x5-0021, x5-6154 or at

Document last modified on September 15, 1995