Comp. Sci. 691T: Descriptive Complexity, Spring, 1997
Meeting Times: MW 2:05-3:20, LGRC: A339
Instructors: David Mix
Barrington and Neil Immerman
Descriptive complexity is an approach, based on mathematical logic, to
classifying the relative difficulty of computational problems (particularly
queries to a database). While traditional complexity theory concentrates
on the resources needed to compute the answer to a query, descriptive
complexity focuses on the resources needed to describe the query in
some logical formalism --- how many variables, how many quantifiers, which
forms of induction, and so forth. Surprisingly, computational complexity
classes like P and NP have natural characterizations in descriptive
complexity, as do all other well-studied complexity classes.
In this seminar we will:
- Describe the logical formalism used for queries and its various
resource measures,
- Prove characterizations of several important computational complexity
classes in terms of descriptive complexity,
- Use pebble games to prove upper and lower bounds on the descriptive
complexity of some important queries, and
- Examine extensions to the model, such as dynamic complexity ,
which measures the descriptive complexity of processing updates and
queries to a database.
- The applications that we investigate will depend on the interests of
those who attend.
Text: We will use Neil Immerman's forthcoming book, Descriptive Complexity,
to appear in Springer-Verlag's series of graduate texts in computer
science.
Prerequisite: CMPSCI 601 or equivalent.
Handouts:
- The first handout is the first three chapters of the book. Come by Neil's
office if you need one.