{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T20:47:12Z","timestamp":1648932432894},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3388,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,12]]},"abstract":"<jats:title>Abstract.<\/jats:title><jats:p>We use finite model theory (in particular, the method of FM-truth definitions, introduced in [MM01] and developed in [K04], and a normal form result akin to those of [Ste93] and [G97]) to prove:<\/jats:p><jats:p>Let <jats:italic>m<\/jats:italic> \u2265 2. Then:<\/jats:p><jats:p>(A) If there exists <jats:italic>k<\/jats:italic> such that NP\u2286 \u03a3<jats:sub><jats:italic>m<\/jats:italic><\/jats:sub> TIME(<jats:italic>n<jats:sup>k<\/jats:sup><\/jats:italic>)\u2229 \u03a0<jats:sub><jats:italic>m<\/jats:italic><\/jats:sub> TIME(<jats:italic>n<jats:sup>k<\/jats:sup><\/jats:italic>), then for every <jats:italic>r<\/jats:italic> there exists <jats:italic>k<\/jats:italic><jats:sub>r<\/jats:sub> such that <jats:bold><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007416_inline1\" \/><\/jats:bold>:<\/jats:p><jats:p>(B) If there exists a superpolynomial time-constructible function <jats:italic>f<\/jats:italic> such that NTIME(<jats:italic>f<\/jats:italic>)<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007416_inline4\" \/>, then additionally <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007416_inline2\" \/>.<\/jats:p><jats:p>This strengthens a result by Mocas [M96] that for any <jats:italic>r<\/jats:italic>, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007416_inline3\" \/>.<\/jats:p><jats:p>In addition, we use FM-truth definitions to give a simple sufficient condition for the <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007416_inline5\" \/> arity hierarchy to be strict over finite models.<\/jats:p>","DOI":"10.2178\/jsl\/1102022213","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:49:24Z","timestamp":1109800164000},"page":"1105-1116","source":"Crossref","is-referenced-by-count":5,"title":["A finite model-theoretical proof of a property of bounded query classes within PH"],"prefix":"10.1017","volume":"69","author":[{"given":"Leszek Aleksander","family":"Ko\u0142odziejczyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007416_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"S0022481200007416_ref006","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210117"},{"key":"S0022481200007416_ref010","first-page":"183\u2013200","volume":"69","author":"Kolodziejczyk","year":"2004","journal-title":"Truth definitions in finite models"},{"key":"S0022481200007416_ref007","first-page":"50\u201357","volume-title":"Proceedings of the Structure in Complexity Theory Conference","author":"Fu","year":"1992"},{"key":"S0022481200007416_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8190-2"},{"key":"S0022481200007416_ref014","first-page":"1\u201322","article-title":"The polynomial-time hierarchy","volume":"3","author":"Stockmeyer","year":"1977","journal-title":"Theoretical Computer Science"},{"key":"S0022481200007416_ref003","first-page":"263\u2013273","volume-title":"ICALP proceedings","author":"Buhrman","year":"1994"},{"key":"S0022481200007416_ref015","doi-asserted-by":"publisher","DOI":"10.1137\/0219058"},{"key":"S0022481200007416_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90075-D"},{"key":"S0022481200007416_ref005","first-page":"43\u201373","volume-title":"Complexity of Computation, SIAM-AMS Proceedings","volume":"7","author":"Fagin","year":"1974"},{"key":"S0022481200007416_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22156-3"},{"key":"S0022481200007416_ref008","first-page":"545\u2013574","volume":"62","author":"Gottlob","year":"1997","journal-title":"Relativized logspace and generalized quantifiers over finite ordered structures"},{"key":"S0022481200007416_ref012","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3870(200111)47:4<513::AID-MALQ513>3.0.CO;2-J"},{"key":"S0022481200007416_ref013","first-page":"65\u201392","article-title":"Logical characterizations of bounded query classes, I. Logspace oracle machines","volume":"18","author":"Stewart","year":"1993","journal-title":"Fundamenta Informaticae"},{"key":"S0022481200007416_ref011","first-page":"221\u2013231","article-title":"Separating classes in the exponential-time hierarchy from classes in","volume":"158","author":"Mocas","year":"1996","journal-title":"PH, Theoretical Computer Science"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T19:39:10Z","timestamp":1557171550000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007416\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,12]]}},"alternative-id":["S0022481200007416"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1102022213","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,12]]}}}