{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,12]],"date-time":"2025-03-12T19:10:22Z","timestamp":1741806622244,"version":"3.38.0"},"reference-count":16,"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":832,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every<jats:italic>n<\/jats:italic>the number of nonisomorphic structures of cardinality at most<jats:italic>n<\/jats:italic>in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees.<\/jats:p>","DOI":"10.2178\/jsl\/1318338855","type":"journal-article","created":{"date-parts":[[2011,10,11]],"date-time":"2011-10-11T14:32:16Z","timestamp":1318343536000},"page":"1381-1402","source":"Crossref","is-referenced-by-count":6,"title":["Strong isomorphism reductions in complexity theory"],"prefix":"10.1017","volume":"76","author":[{"given":"Sam","family":"Buss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yijia","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Flum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sy-David","family":"Friedman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moritz","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200001432_ref016","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45303-2"},{"key":"S0022481200001432_ref014","first-page":"364","volume-title":"Proceedings of mathematical foundations of computer science, (MFCS'84)","volume":"176","author":"Kowalczyk","year":"1984"},{"key":"S0022481200001432_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90022-9"},{"key":"S0022481200001432_ref011","first-page":"115","article-title":"From invariants to canonization","volume":"63","author":"Gurevich","year":"1997","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"volume-title":"Lecture at the Kurt Godel Research Center","year":"2009","author":"Friedman","key":"S0022481200001432_ref009"},{"key":"S0022481200001432_ref008","first-page":"894","volume":"54","author":"Friedman","year":"1989","journal-title":"A Borel reducibility theory for classes of countable structures"},{"volume-title":"Finite model theory","year":"1999","author":"Ebbinghaus","key":"S0022481200001432_ref006"},{"key":"S0022481200001432_ref005","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/978-3-642-14162-1_27","volume-title":"Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP'10)","volume":"6199","author":"Chen","year":"2010"},{"key":"S0022481200001432_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"S0022481200001432_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13331-3_31"},{"key":"S0022481200001432_ref002","doi-asserted-by":"publisher","DOI":"10.1137\/0213042"},{"key":"S0022481200001432_ref001","doi-asserted-by":"publisher","DOI":"10.1090\/S1079-6762-01-00087-7"},{"volume-title":"Complexity classes of equivalence problems revisited","year":"2009","author":"Fortnow","key":"S0022481200001432_ref007"},{"key":"S0022481200001432_ref013","first-page":"277","volume-title":"Proceedings of the 23rd conference on foundations of software technology and theoretical computer science (FSTTCS'02)","volume":"2914","author":"Kavitha","year":"2003"},{"key":"S0022481200001432_ref015","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804670"},{"volume-title":"Introduction to Boolean algebras","year":"2008","author":"Givant","key":"S0022481200001432_ref010"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200001432","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,12]],"date-time":"2025-03-12T18:32:15Z","timestamp":1741804335000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200001432\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["S0022481200001432"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1318338855","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"type":"print","value":"0022-4812"},{"type":"electronic","value":"1943-5886"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}