Descriptive complexity measures the richness of logical languages that are
needed to describe computational tasks. All natural complexity classes
have been
characterized by natural descriptive measures. Descriptive complexity
provides a
rich and elegant theory which has resulted in a number of new insights
and results
concerning complexity. In this talk I will survey some of the main
high points of
descriptive complexity and discuss some of the new research directions
including
dynamic complexity and descriptive programming. This would be a good
introduction to
the subject for anyone interested in taking CMPSCI 741: the complexity
theory seminar
that Dave Barrington and I will teach in spring 2003.
Last modified 20 October 2002