Capturing Complexity Classes Using Generalized Quantifiers

Argimiro A Arratia Quesada

(Universidad Simon Bolivar, Caracas and University of Leicester)

I will describe a technique, first developed by Immerman (1980's) and later exploited by Stewart, and Stewart and myself, for syntactically interpret the computational complexity classes log-space, nondeterministic log-space, P, NP and Polynomial Space, via extensions of first order logic (FO) by generalized quantifiers (or Lindstrom's quantifiers) corresponding to complete problems in the respective complexity classes listed above. I will explain a collapsing property for the logics thus formed, which occurs with respect to ordered finite structures, and then explain in the case of PSPACE, what happen if the order is not present. This is all Finite Model Theory. Loads of hand-waving, loads of fun.
Tuesday 21st October 1997, 14:30
Seminar Room 322
Department of Computer Science