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:

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: