{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:50Z","timestamp":1750306370593,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,5,11]],"date-time":"2016-05-11T00:00:00Z","timestamp":1462924800000},"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":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2016,5,25]]},"abstract":"<jats:p>We investigate autoreducibility properties of complete sets for NEXP under different polynomial-time reductions. Specifically, we show under some polynomial-time reductions that there are complete sets for NEXP that are not autoreducible. We obtain the following main results:<\/jats:p>\n          <jats:p>\n            \u2014For any positive integers\n            <jats:italic>s<\/jats:italic>\n            and\n            <jats:italic>k<\/jats:italic>\n            such that 2\n            <jats:sup>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sup>\n            \u2212 1 &gt;\n            <jats:italic>k<\/jats:italic>\n            , there is a \u2264\n            <jats:sub>s-T<\/jats:sub>\n            <jats:sup>p<\/jats:sup>\n            -complete set for NEXP that is not \u2264\n            <jats:sub>k-tt<\/jats:sub>\n            <jats:sup>p<\/jats:sup>\n            -autoreducible.\n          <\/jats:p>\n          <jats:p>\n            \u2014For every constant\n            <jats:italic>c<\/jats:italic>\n            &gt; 1, there is a \u2264\n            <jats:sub>2-T<\/jats:sub>\n            <jats:sup>p<\/jats:sup>\n            -complete set for NEXP that is not autoreducible under nonadaptive reductions that make no more than three queries, such that each of them has a length between\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\/c<\/jats:sup>\n            and\n            <jats:italic>\n              n\n              <jats:sup>c<\/jats:sup>\n            <\/jats:italic>\n            , where\n            <jats:italic>n<\/jats:italic>\n            is input size.\n          <\/jats:p>\n          <jats:p>\n            \u2014For any positive integer\n            <jats:italic>k<\/jats:italic>\n            , there is a \u2264\n            <jats:sub>k-tt<\/jats:sub>\n            <jats:sup>p<\/jats:sup>\n            -complete set for NEXP that is not autoreducible under \u2264\n            <jats:sub>k-tt<\/jats:sub>\n            <jats:sup>p<\/jats:sup>\n            -reductions whose truth table is not a disjunction or a negated disjunction.\n          <\/jats:p>\n          <jats:p>\n            Finally, we show that settling the question of whether every \u2264\n            <jats:sub>dtt<\/jats:sub>\n            <jats:sup>p<\/jats:sup>\n            -complete set for NEXP is \u2264\n            <jats:sub>NOR-tt<\/jats:sub>\n            <jats:sup>p<\/jats:sup>\n            -autoreducible either positively or negatively would lead to major results about the exponential time complexity classes.\n          <\/jats:p>","DOI":"10.1145\/2898440","type":"journal-article","created":{"date-parts":[[2016,5,13]],"date-time":"2016-05-13T14:30:58Z","timestamp":1463149858000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Structural Properties of Nonautoreducible Sets"],"prefix":"10.1145","volume":"8","author":[{"given":"Dung","family":"Nguyen","sequence":"first","affiliation":[{"name":"LogicBlox Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan L.","family":"Selman","sequence":"additional","affiliation":[{"name":"University at Buffalo, Buffalo, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,5,11]]},"reference":[{"volume-title":"Logic and Machines","series-title":"Lecture Notes in Computer Science","author":"Ambos-Spies K.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01276436"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798334736"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090397"},{"volume-title":"Proceedings of the 9th Annual IEEE Structure in Complexity Theory Conference, 1994","year":"1994","author":"Buhrman H.","key":"e_1_2_1_5_1"},{"volume-title":"IEEE Structure in Complexity Theory Conference. IEEE Computer Society, 196--207","author":"Downey R.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01276436"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_40"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.020"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/23005.23009"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"S. Homer and A. Selman. 2011. Computability and Complexity Theory (2nd ed.). Springer. I--XVI 1--298 pages.   S. Homer and A. Selman. 2011. Computability and Complexity Theory (2nd ed.). Springer. I--XVI 1--298 pages.","DOI":"10.1007\/978-1-4614-0682-2_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274765"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"volume":"25","volume-title":"Ernst W. Mayr and Natacha Portier (Eds.)","author":"Nguyen D.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","first-page":"814","article-title":"On autoreducibility. Dokl. Akad. Nauk SSSR 192 (1970)","volume":"11","author":"Trahtenbrot B.","year":"1970","journal-title":"Translation in Soviet Math. Dokl."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898440","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2898440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:30Z","timestamp":1750222590000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898440"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,11]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,5,25]]}},"alternative-id":["10.1145\/2898440"],"URL":"https:\/\/doi.org\/10.1145\/2898440","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2016,5,11]]},"assertion":[{"value":"2015-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}