Repository | Series | Book | Chapter
Capturing relativized complexity classes with Lindström quantifiers
pp. 133-140
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].
Publication details
Published in:
Depauli Schimanovich Werner, Köhler Eckehart, Stadler Friedrich (1995) The foundational debate: complexity and constructivity in mathematics and physics. Dordrecht, Springer.
Pages: 133-140
DOI: 10.1007/978-94-017-3327-4_10
Full citation:
Makowsky Janos 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, 133–140.