{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,31]],"date-time":"2024-01-31T13:13:20Z","timestamp":1706706800985},"reference-count":8,"publisher":"Duke University Press","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Notre Dame J. Formal Logic"],"published-print":{"date-parts":[[2017,1,1]]},"DOI":"10.1215\/00294527-3867118","type":"journal-article","created":{"date-parts":[[2017,3,3]],"date-time":"2017-03-03T03:02:10Z","timestamp":1488510130000},"source":"Crossref","is-referenced-by-count":2,"title":["On Polynomial-Time Relation Reducibility"],"prefix":"10.1215","volume":"58","author":[{"given":"Su","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Caleb","family":"Ziegler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"73","reference":[{"key":"4","unstructured":"[4] J. Finkelstein and B. Hescott, \u201cPolynomial time kernel reductions,\u201d preprint, <a href=\"arxiv:1604.08558v1\">arxiv:1604.08558v1<\/a> [cs.CC]."},{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] A. Blass and Y. Gurevich, \u201cEquivalence relations, invariants, and normal forms,\u201d <i>SIAM Journal on Computing<\/i>, vol. 13 (1984), pp. 682\u201389.","DOI":"10.1137\/0213042"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] A. Blass and Y. Gurevich, \u201cEquivalence relations, invariants, and normal forms, II,\u201d pp. 24\u201342 in <i>Logic and Machines: Decision Problems and Complexity (M\u00fcnster, 1983)<\/i>, vol. 171 of <i>Lecture Notes in Computer Science<\/i>, Springer, Berlin, 1984.","DOI":"10.1007\/3-540-13331-3_31"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] S. Buss, Y. Chen, J. Flum, S.-D. Friedman, and M. M\u00fcller, \u201cStrong isomorphism reductions in complexity theory,\u201d <i>Journal of Symbolic Logic<\/i>, vol. 76 (2011), pp. 1381\u20131402.","DOI":"10.2178\/jsl\/1318338855"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] L. Fortnow and J. A. Grochow, \u201cComplexity classes of equivalence problems revisited,\u201d <i>Information and Computation<\/i>, vol. 209 (2011), pp. 748\u201363.","DOI":"10.1016\/j.ic.2011.01.006"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] J. E. Hopcroft and R. E. Tarjan, \u201cIsomorphism of planar graphs,\u201d pp. 131\u2013152, 187\u2013212 in <i>Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972)<\/i>, edited by R. E. Miller and J. W. Thatcher, Plenum, New York, 1972.","DOI":"10.1007\/978-1-4684-2001-2_13"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] G. L. Miller, \u201cGraph isomorphism, general remarks,\u201d <i>Journal of Computer and System Sciences<\/i>, vol. 18 (1979), pp. 128\u201342.","DOI":"10.1016\/0022-0000(79)90043-6"},{"key":"8","unstructured":"[8] C. H. Papadimitriou, <i>Computational Complexity<\/i>, Addison-Wesley, Reading, Mass., 1994."}],"container-title":["Notre Dame Journal of Formal Logic"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/journalArticle\/Download?urlid=10.1215\/00294527-3867118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T20:59:14Z","timestamp":1706648354000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/notre-dame-journal-of-formal-logic\/volume-58\/issue-2\/On-Polynomial-Time-Relation-Reducibility\/10.1215\/00294527-3867118.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,1]]},"references-count":8,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2017,1,1]]}},"URL":"https:\/\/doi.org\/10.1215\/00294527-3867118","relation":{},"ISSN":["0029-4527"],"issn-type":[{"value":"0029-4527","type":"print"}],"subject":[],"published":{"date-parts":[[2017,1,1]]}}}