Capturing Relativized Complexity Classes without Order

Mathematical Logic Quarterly 44 (1):109-122 (1998)
  Copy   BIBTEX


We consider the problem of obtaining logical characterisations of oracle complexity classes. In particular, we consider the complexity classes LOGSPACENP and PTIMENP. For these classes, characterisations are known in terms of NP computable Lindström quantifiers which hold on ordered structures. We show that these characterisations are unlikely to extend to arbitrary structures, since this would imply the collapse of certain exponential complexity hierarchies. We also observe, however, that PTIMENP can be characterised in terms of Lindström quantifers , though it remains open whether this can be done for LOGSPACENP



    Upload a copy of this work     Papers currently archived: 74,389

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
Elementary Properties of the Finite Ranks.Anuj Dawar, Kees Doets, Steven Lindell & Scott Weinstein - 1998 - Mathematical Logic Quarterly 44 (3):349-353.
Arithmetical Definability Over Finite Structures.Troy Lee - 2003 - Mathematical Logic Quarterly 49 (4):385.
The Hierarchy Theorem for Second Order Generalized Quantifiers.Juha Kontinen - 2006 - Journal of Symbolic Logic 71 (1):188 - 202.
On Vectorizations of Unary Generalized Quantifiers.Kerkko Luosto - 2012 - Archive for Mathematical Logic 51 (3-4):241-255.
Space Complexity of Abelian Groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2009 - Archive for Mathematical Logic 48 (1):115-140.
Computational Semantics for Monadic Quantifiers.Marcin Mostowski - 1998 - Journal of Applied Non--Classical Logics 8 (1-2):107--121.


Added to PP

40 (#289,210)

6 months
1 (#415,900)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Generalized Quantifiers.Dag Westerståhl - 2008 - Stanford Encyclopedia of Philosophy.

Add more citations

References found in this work

Finite Model Theory.Heinz-Dieter Ebbinghaus & Jörg Flum - 2001 - Studia Logica 69 (3):449-449.
Finite Model Theory.Heinz-Dieter Ebbinghaus & Torg Flum - 1997 - Studia Logica 58 (2):332-335.

Add more references