Capturing relativized complexity classes with Lindström quantifiers

Janos A. Makowsky

pp. 133-140

in: Werner Depauli Schimanovich, Eckehart Köhler, Friedrich Stadler (eds), The foundational debate, Berlin, Springer, 1995

Abstract

In the last 20 years several logics were exhibited which capture complexity classes such as L (LogSpace), NL (Non-deterministic LogSpace), P (Polynomial Time), NP (Non-deterministic Polynomial Time), PH (the polynomial hierarchy), [4, 12, 13, 23, 20] on ordered structures. In mathematical logic the theory of abstract model theory and Lindström quantifiers is well established [2]. In this talk we report our work concerning unification of Descriptive Complexity Theory and Abstract Model Theory. A detailed account has been published in [15, 16, 17]. Similar results with complementary aims have been proven recently by G. Gottlob, [6].