{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T02:54:56Z","timestamp":1649213696362},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3663,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We show that there is a structure of countably infinite signature with <jats:italic>P<\/jats:italic> = <jats:italic>N<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>P<\/jats:italic> and a structure of finite signature with <jats:italic>P<\/jats:italic> = <jats:italic>N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>P<\/jats:italic> and <jats:italic>N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>P \u2260 N<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>P<\/jats:italic>. We give a further example of a structure of finite signature with <jats:italic>P \u2260 N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>P<\/jats:italic> and <jats:italic>N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>P \u2260 N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>P<\/jats:italic>. Together with a result from [10] this implies that for each possibility of <jats:italic>P<\/jats:italic> versus <jats:italic>NP<\/jats:italic> over structures there is an example of countably infinite signature. Then we show that for some finite <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007994_inline1\" \/> the class of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007994_inline1\" \/>-structures with <jats:italic>P<\/jats:italic> = <jats:italic>N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>P<\/jats:italic> is not closed under ultraproducts and obtain as corollaries that this class is not \u2206-elementary and that the class of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007994_inline1\" \/>-structures with <jats:italic>P \u2260 N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>P<\/jats:italic> is not elementary. Finally we prove that for all \u0192 dominating all polynomials there is a structure of finite signature with the following properties: <jats:italic>P \u2260 N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>P<\/jats:italic>, <jats:italic>N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>P \u2260 N<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>P<\/jats:italic>, the levels <jats:italic>N<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>TIME<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup><jats:italic>i<\/jats:italic><\/jats:sup>) of <jats:italic>N<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>P<\/jats:italic> and the levels <jats:italic>N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>TIME<\/jats:italic>(<jats:italic>n<jats:sup>i<\/jats:sup><\/jats:italic>) of <jats:italic>N<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>P<\/jats:italic> are different for different <jats:italic>i<\/jats:italic>, indeed <jats:italic>DTIME<\/jats:italic>(<jats:italic>n<jats:sup>i\u2032<\/jats:sup>) \u2288 N<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>TIME<\/jats:italic>(<jats:italic>n<jats:sup>i<\/jats:sup><\/jats:italic>) if <jats:italic>i<\/jats:italic> \u2032 &gt; <jats:italic>i<\/jats:italic>; <jats:italic>DTIME(\u0192) \u2288 N<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>P<\/jats:italic>, and <jats:italic>N<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>P \u2288 DEC<\/jats:italic>. <jats:italic>DEC<\/jats:italic> is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of <jats:italic>N<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>P<\/jats:italic> is analyzed in a more detailed way. In our proofs we use methods in the style of classical computability theory to construct structures except for one use of ultraproducts.<\/jats:p>","DOI":"10.2178\/jsl\/1080938824","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:24:53Z","timestamp":1109798693000},"page":"39-64","source":"Crossref","is-referenced-by-count":2,"title":["<i>P<\/i> versus <i>NP<\/i> and computability theoretic constructions in complexity theory over algebraic structures"],"prefix":"10.1017","volume":"69","author":[{"given":"Gunther","family":"Mainhardt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007994_ref005","volume-title":"Mathematical logic","author":"Ebbinghaus","year":"1984"},{"key":"S0022481200007994_ref009","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3870(200101)47:1<67::AID-MALQ67>3.0.CO;2-V"},{"key":"S0022481200007994_ref001","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"S0022481200007994_ref004","volume-title":"Model theory","author":"Chang","year":"1990"},{"key":"S0022481200007994_ref011","volume-title":"On structures with proper polynomial time hierarchy","author":"Mainhardt","year":"2002"},{"key":"S0022481200007994_ref007","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19980440102"},{"key":"S0022481200007994_ref006","volume-title":"Computability and complexity over structures of finite type","author":"Hemmerling","year":"1995"},{"key":"S0022481200007994_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)00063-B"},{"key":"S0022481200007994_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200007994_ref003","volume-title":"Models and ultraproducts","author":"Bell","year":"1969"},{"key":"S0022481200007994_ref012","first-page":"235","volume":"67","author":"Prunescu","year":"2002","journal-title":"A model-theoretic proof for P \u2260 NP over all infinite abelian groups"},{"key":"S0022481200007994_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97062-7"},{"key":"S0022481200007994_ref008","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19980440311"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007994","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T21:28:52Z","timestamp":1557178132000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007994\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,3]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,3]]}},"alternative-id":["S0022481200007994"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1080938824","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,3]]}}}