{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:33Z","timestamp":1750306713737,"version":"3.41.0"},"reference-count":79,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,9,17]],"date-time":"2014-09-17T00:00:00Z","timestamp":1410912000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2014,9,17]]},"DOI":"10.1145\/2670418.2670436","type":"journal-article","created":{"date-parts":[[2014,9,19]],"date-time":"2014-09-19T12:27:17Z","timestamp":1411129637000},"page":"54-70","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Beautiful structures"],"prefix":"10.1145","volume":"45","author":[{"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[{"name":"University of Rochester, Rochester, NY"}]}],"member":"320","published-online":{"date-parts":[[2014,9,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00167-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803405"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715929"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5937"},{"volume-title":"Cornell University","year":"1977","author":"Berman L.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200057"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1115"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213030"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90053-4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90061-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646503.759210"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/038\/1020809"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1056010"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90043-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80084-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.01.002"},{"key":"e_1_2_1_19_1","unstructured":"Clay Mathematics Institute. www.claymath.org\/millennium-problems. URL verified June 2014.  Clay Mathematics Institute. www.claymath.org\/millennium-problems. URL verified June 2014."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032916"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80056-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793248305"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793247439"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_27"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90199-8"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220033"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2696081.2696095"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_40"},{"issue":"3","key":"e_1_2_1_29_1","first-page":"61","article-title":"Autoreducibility and mitocity","volume":"40","author":"Glaser C.","year":"2009","journal-title":"SIGACT News"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217018"},{"volume-title":"MIT Press","year":"1987","author":"H\u00e1stad J.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","first-page":"144","article-title":"Relativization: A revisionistic retrospective","volume":"47","author":"Hartmanis J.","year":"1992","journal-title":"Bulletin of the EATCS"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220071"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054195000214"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0061"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268315"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/502976"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1815"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_40"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90318-A"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1613"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90023-C"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/284842"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"S. Homer and A. Selman. Computability and Complexity Theory. Springer-Verlag 2nd edition 2011.   S. Homer and A. Selman. Computability and Complexity Theory. Springer-Verlag 2nd edition 2011.","DOI":"10.1007\/978-1-4614-0682-2"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/572575"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0220595-7"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804678"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90013-2"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90085-4"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90085-8"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5938"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1972.29"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00060-7"},{"key":"e_1_2_1_56_1","first-page":"590","volume-title":"Proceedings of the 31st Annual Symposium on Theoretical Aspects of Computer Science","author":"Nguyen D.","year":"2014"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793258131"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220030"},{"key":"e_1_2_1_59_1","unstructured":"C. Papadimitriou. Computational Complexity. Addison-Wesley 1994.  C. Papadimitriou. Computational Complexity. Addison-Wesley 1994."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1486"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00186-5"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90027-2"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01704904"},{"issue":"5","key":"e_1_2_1_64_1","first-page":"A-498","article-title":"On the structure of NP","volume":"21","author":"Selman A.","year":"1974","journal-title":"Notices of the AMS"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207035"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744288"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90068-4"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)80084-3"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90039-1"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217062"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01374525"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80009-1"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.5555\/791229.792261"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212037"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90097-1"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90071-3"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.5555\/4479.4487"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2670418.2670436","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2670418.2670436","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:20Z","timestamp":1750231160000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2670418.2670436"}},"subtitle":["an appreciation of the contributions of Alan Selman"],"short-title":[],"issued":{"date-parts":[[2014,9,17]]},"references-count":79,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,9,17]]}},"alternative-id":["10.1145\/2670418.2670436"],"URL":"https:\/\/doi.org\/10.1145\/2670418.2670436","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2014,9,17]]},"assertion":[{"value":"2014-09-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}