{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T07:19:50Z","timestamp":1719213590600},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2009,9,25]]},"abstract":"Autoreducibility and mitoticity express weak forms of redundancy of information that a set might possess. We describe many results known about these concepts. Mitoticity always implies autoreducibility, but the converse holds in some situations and fails in others. Among the results we describe are that NP-complete sets are many-one autoreducible and that every many-one autoreducible set is many-one mitotic. In particular, every infinite NPcomplete set splits by a set in P into two disjoint, infinite NP-complete set.<\/jats:p>","DOI":"10.1145\/1620491.1620505","type":"journal-article","created":{"date-parts":[[2009,10,6]],"date-time":"2009-10-06T18:18:59Z","timestamp":1254853139000},"page":"60-76","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["SIGACT news complexity theory column 64"],"prefix":"10.1145","volume":"40","author":[{"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[{"name":"University of Rochester, Rochester, NY"}]}],"member":"320","published-online":{"date-parts":[[2009,9,25]]},"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.1109\/SFCS.1992.267823"},{"key":"e_1_2_1_3_1","volume-title":"Springer-Verlag","author":"Ambos-Spies K.","year":"1984"},{"key":"e_1_2_1_5_1","volume-title":"Cornell University","author":"Berman L.","year":"1977"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01276436"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798334736"},{"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.1145\/73007.73015"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1115"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30550-7_8"},{"key":"e_1_2_1_12_1","unstructured":"B. Borchert H. Schmitz and F. Stephan. Unpublished manuscript 1999. B. Borchert H. Schmitz and F. Stephan. Unpublished manuscript 1999."},{"key":"e_1_2_1_13_1","first-page":"41","article-title":"A Post's program for complexity theory","volume":"85","author":"Buhrman H.","year":"2005","journal-title":"Bulletin of the EATCS"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054191000054"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764903"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129775"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221044"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.020"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/060673886"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301309"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90195-2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.043"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1993.336526"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19670130102"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_27_1","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"191","volume-title":"Distributed Computing and Cryptography","author":"Lipton R.","year":"1991"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90002-2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793258131"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174648"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220030"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"issue":"6","key":"e_1_2_1_33_1","first-page":"1224","article-title":"On autoreducibility","volume":"192","author":"Trakhtenbrot B.","year":"1970","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_2_1_34_1","volume-title":"Studienarbeit","author":"Travers S.","year":"2002"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873197"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/22101.22108"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1620491.1620505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T09:26:48Z","timestamp":1672306008000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1620491.1620505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,25]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,9,25]]}},"alternative-id":["10.1145\/1620491.1620505"],"URL":"http:\/\/dx.doi.org\/10.1145\/1620491.1620505","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2009,9,25]]},"assertion":[{"value":"2009-09-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
