Book | Chapter
(1995) The foundational debate, Dordrecht, Springer.
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].
Publication details
DOI: 10.1007/978-94-017-3327-4_10
Full citation:
Makowsky, J. A. (1995)., Capturing relativized complexity classes with Lindström quantifiers, in W. Depauli Schimanovich, E. Köhler & F. Stadler (eds.), The foundational debate, Dordrecht, Springer, pp. 133-140.
This document is unfortunately not available for download at the moment.