{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T02:47:51Z","timestamp":1688611671125},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3479,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,9]]},"abstract":"<jats:title>Abstract.<\/jats:title><jats:p>A set <jats:italic>A<\/jats:italic> is <jats:italic>m-reducible<\/jats:italic> (or Karp-reducible) to <jats:italic>B<\/jats:italic> if and only if there is a polynomial-time computable function <jats:italic>f<\/jats:italic> such that, for all <jats:italic>x, x<\/jats:italic> \u2208 <jats:italic>A<\/jats:italic> if and only if <jats:italic>f(x)<\/jats:italic> \u2208 <jats:italic>B<\/jats:italic>. Two sets are:<\/jats:p><jats:p>\u2022 <jats:italic>1-equivalent<\/jats:italic> if and only if each is m-reducible to the other by one-one reductions;<\/jats:p><jats:p>\u2022 <jats:italic>p-invertible equivalent<\/jats:italic> if and only if each is m-reducible to the other by one-one, polynomial-time invertible reductions; and<\/jats:p><jats:p>\u2022 <jats:italic>p-isumorphic<\/jats:italic> if and only if there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible.<\/jats:p><jats:p>In this paper we show the following characterization.<\/jats:p><jats:p>Theorem. <jats:italic>The following are equivalent:<\/jats:italic><\/jats:p><jats:p>(a) <jats:italic>P = PSPACE<\/jats:italic>.<\/jats:p><jats:p>(b) <jats:italic>Every two<\/jats:italic> 1-<jats:italic>equivalent sets are p-isomorphic<\/jats:italic>.<\/jats:p><jats:p>(c) <jats:italic>Every two p-invertible equivalent sets are p-isomorphic<\/jats:italic>.<\/jats:p>","DOI":"10.2178\/jsl\/1096901763","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:41:53Z","timestamp":1109799713000},"page":"713-741","source":"Crossref","is-referenced-by-count":1,"title":["Every polynomial-time 1-degree collapses if and only if P = PSPACE"],"prefix":"10.1017","volume":"69","author":[{"given":"Stephen A.","family":"Fenner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stuart A.","family":"Kurtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James S.","family":"Royer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007593_ref011","doi-asserted-by":"publisher","DOI":"10.1137\/0217018"},{"key":"S0022481200007593_ref004","volume-title":"Was sind und was sollen die Zahlen?","volume":"2","author":"Dedekind","year":"1888"},{"key":"S0022481200007593_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-5049-0"},{"key":"S0022481200007593_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_7"},{"key":"S0022481200007593_ref001","doi-asserted-by":"publisher","DOI":"10.1137\/0218053"},{"key":"S0022481200007593_ref016","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9478-5"},{"key":"S0022481200007593_ref002","unstructured":"Berman L. , Polynomial reducibilities and complete sets, Ph.D. thesis , Cornell University, 1977."},{"key":"S0022481200007593_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90152-0"},{"key":"S0022481200007593_ref003","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"S0022481200007593_ref006","volume-title":"From Kant to Hilbert: A sourcebook in the foundations of mathematics","author":"Ewald","year":"1996"},{"key":"S0022481200007593_ref009","volume-title":"Computers and intractability","author":"Garey","year":"1979"},{"key":"S0022481200007593_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90126-E"},{"key":"S0022481200007593_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90085-4"},{"key":"S0022481200007593_ref017","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19550010205"},{"key":"S0022481200007593_ref018","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200007593_ref005","volume-title":"Technical Report LCSR-TR-34","author":"Dowd","year":"1982"},{"key":"S0022481200007593_ref010","first-page":"495","volume-title":"Proceedings of the 25th annual ieee symposium on foundations of computer science","author":"Grollmann","year":"1984"},{"key":"S0022481200007593_ref008","first-page":"240","volume-title":"Proceedings of the symposium on theoretical aspects of computer science","author":"Ganesan","year":"1989"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T20:26:45Z","timestamp":1557174405000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007593\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,9]]}},"alternative-id":["S0022481200007593"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1096901763","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,9]]}}}