Development and Application of Descriptive Complexity

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

Descriptive Complexity measures the richness of a language or sentence needed to describe a given property. The languages are variants of first-order logic and their targets are finite, ordered structures. There is a profound relationship between the traditional computational complexity of a problem and the descriptive complexity of the problem; indeed, all major complexity classes have been shown to have natural descriptive characterizations. This means that complexity can be understood entirely from a logical point of view. As a consequence, important new understandings about complexity have arisen from the descriptive point of view. The current research involves three major topics: (a) The theory of dynamic complexity, which is especially appropriate for database complexity, is being studied. Complete problems for dynamic complexity classes are being developed and the complexity of important dynamic problems such as graph reachability are being investigated; (b) Promising new methods for proving lower bounds techniques on the descriptive complexity of problems have been developed and are now being extended; and finally, (c) A Descriptive Programming environment is being developed in which the computational complexity of checking whether an input satisfies the properties being described can be read from the face of the description.