{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:24:14Z","timestamp":1762100654073},"reference-count":28,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3238,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the problem of obtaining logical characterisations of oracle complexity classes. In particular, we consider the complexity classes LOGSPACE<jats:sup>NP<\/jats:sup> and PTIME<jats:sup>NP<\/jats:sup>. For these classes, characterisations are known in terms of NP computable Lindstr\u00f6m quantifiers which hold on ordered structures. We show that these characterisations are unlikely to extend to arbitrary (unordered) structures, since this would imply the collapse of certain exponential complexity hierarchies. We also observe, however, that PTIME<jats:sup>NP<\/jats:sup> can be characterised in terms of Lindstr\u00f6m quantifers (not necessarily NP computable), though it remains open whether this can be done for LOGSPACE<jats:sup>NP<\/jats:sup>.<\/jats:p>","DOI":"10.1002\/malq.19980440108","type":"journal-article","created":{"date-parts":[[2007,5,31]],"date-time":"2007-05-31T02:48:19Z","timestamp":1180579699000},"page":"109-122","source":"Crossref","is-referenced-by-count":6,"title":["Capturing Relativized Complexity Classes without Order"],"prefix":"10.1002","volume":"44","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[]},{"given":"Lauri","family":"Hella","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90032-Z"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.2307\/2272133"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213042"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/5.2.213"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1166"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03182-7"},{"key":"e_1_2_1_8_2","series-title":"SIAM\u2010AMS Proceedings 7","first-page":"43","volume-title":"Complexity of Computation","author":"Fagin R.","year":"1974"},{"key":"e_1_2_1_9_2","article-title":"Relativized logspace and generalized quantifiers over ordered finite structures","author":"Gottlob G.","journal-title":"J. Symbolic Logic"},{"key":"e_1_2_1_9_3","first-page":"65","volume-title":"Proc. Tenth Annual Symposium on Logic in Computer Science LICS'95 (San Diego, CA, June 1995)","year":"1995"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60246-1_113"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0099486"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90055-2"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90025-1"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00059-X"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217080"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90021-7"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683260"},{"key":"e_1_2_1_20_2","series-title":"Lecture Notes in Computer Science 832","first-page":"198","volume-title":"Computer Science Logic (CSL'93)","author":"Makowsky J. A.","year":"1994"},{"key":"e_1_2_1_21_2","unstructured":"Mocas S. Separating exponential time classes from polynomial time classes. Ph.D. Thesis Graduate School College of Computer Science Northeastern University 1993."},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00078-X"},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","first-page":"65","DOI":"10.3233\/FI-1993-18105","article-title":"Logical characterization of bounded query classes I: Logspace oracle machines","volume":"18","author":"Stewart I. A.","year":"1993","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","first-page":"93","DOI":"10.3233\/FI-1993-18106","article-title":"Logical characterization of bounded query classes II: Polynomial\u2010time oracle machines","volume":"18","author":"Stewart I. A.","year":"1993","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00299636"},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"Vardi M. Y. The complexity of relational query languages. In: Proceedings of the 14th ACM Symposium on the Theory of Computing (1982) pp.137\u2013146.","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90020-8"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/0219058"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19980440108","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19980440108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T12:55:10Z","timestamp":1698497710000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19980440108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1002\/malq.19980440108"],"URL":"https:\/\/doi.org\/10.1002\/malq.19980440108","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}