CSc 85040:  TOPICS IN COMPUTATIONAL COMPLEXITY: LOGIC AND COMPLEXITY THEORY
CRN Code: 68267
3 credits

Tues.,
4:15 - 6:15 pm

Professor Noson Yanofsky

Prerequisites:

This class should be understandable by anyone who knows the very basics of elementary complexity theory (Turing machines, P, NP, NP-Complete, etc.) and the basics of logic (vocabulary, formulas, model, etc.)

Course description:
In this class we examine the amount of complexity needed to logically describe or express certain computational problems. We show that there is a very close connection between the hierarchy of logical languages and the hierarchy of complexity classes. The prototypical example of such a connection is Fagin’s theorem (1974) which shows that NP-time problems can be described by second-order existential statements and second-order existential statements can be checked in NP-time. This gives a machine-independent way of describing complexity classes. We shall study many other logical languages and their related complexity classes. This area of study is called “descriptive complexity theory”.

 Since computers can only store a finite amount of information, when studying logic, we look at various logical languages over the class of finite models.  The most amazing part of “finite model theory” is that most of the classical theorems of model theory fail when one restricts to the subclass of finite models. For example, Trahtenbrot’s theorem (1950) shows that completeness fails for finite models.

Texts:                  1) Descriptive Complexity by Neil Immerman (1998) [Imm]

Recommended:

                        2) Elements of Finite Model Theory by Leonid Libkin. (2004) [Lib]

                        3) Finite Model Theory Second Edition by Heinz-Dieter Ebbinghaus

                                    and Jörg Flum. (2005) [Ebb]

See also         http://www.cs.umass.edu/~immerman/descriptive_complexity.html

                     http://www.math.helsinki.fi/logic/people/jouko.vaananen/shortcourse.pdf

 All three books will be on reserve in the library.

Tentative Schedule:

1) Review of Logic. [Imm 1][Lib 2.1]

2) Review of Complexity Theory. [Imm 2][Lib 2.3]

3) Intro: NP and Second-Order Existential Logic (Fagin’s Theorem). [Imm 7][Lib 9.2]

4) P-time and below. [Imm 3] [Lib 10] [Ebb8]

5) Parallelism [Imm 5]

6) Finite Automata [Lib 7][Ebb 7]

7) Pspace [Imm 10]

8) Ehrenfeucht-Fraïssé Games [Imm 6] [Lib 3][Ebb 2]

9) 0-1 Laws. [Imm 6.5][Lib 12][Ebb 4]

10) Leaf Languages. A universal approach to descriptive complexity theory.

We shall spend a large part of the course making sense of this diagram (shamelessly taken from Neil Immerman’s web page). The hierarchy of complexity theory is given in black and the related hierarchies of logical systems are given in color.