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.
ABOUT THE SPEAKER:
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:
http://dimacs.rutgers.edu/archive/SpecialYears/1995_1996/
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:
http://athos.rutgers.edu/pub/colloquia/
or contact Sven Dickinson (Colloquium Committee Chair) at x5-0021, x5-6154 or at sven@kiva.rutgers.edu.