{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:10Z","timestamp":1750306690097,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,3,1]],"date-time":"2014-03-01T00:00:00Z","timestamp":1393632000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0652601, 0917417, 0830479, 0916797"],"award-info":[{"award-number":["0652601, 0917417, 0830479, 0916797"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2014,3]]},"abstract":"<jats:p>\n            We study the following question: if\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            are disjoint NP-complete sets, then is\n            <jats:italic>A<\/jats:italic>\n            \u222a\n            <jats:italic>B<\/jats:italic>\n            NP-complete? We provide necessary and sufficient conditions under which the union of disjoint NP-complete sets remain complete.\n          <\/jats:p>","DOI":"10.1145\/2591508","type":"journal-article","created":{"date-parts":[[2014,4,1]],"date-time":"2014-04-01T13:06:54Z","timestamp":1396357614000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Unions of Disjoint NP-Complete Sets"],"prefix":"10.1145","volume":"6","author":[{"given":"Christian","family":"Gla\u00dfer","sequence":"first","affiliation":[{"name":"Julius-Maximilians-Universit\u00e4t W\u00fcrzburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John M.","family":"Hitchcock","sequence":"additional","affiliation":[{"name":"University Wyoming"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[{"name":"Iowa State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephan","family":"Travers","sequence":"additional","affiliation":[{"name":"Julius-Maximilians-Universit\u00e4t W\u00fcrzburg"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873198"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80056-X"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics).","volume":"5","author":"Fortnow L.","unstructured":"L. Fortnow , J. H. Lutz , and E. Mayordomo . 2010. Inseparability and strong hypotheses for disjoint NP pairs . In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics). Vol. 5 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 395--404. L. Fortnow, J. H. Lutz, and E. Mayordomo. 2010. Inseparability and strong hypotheses for disjoint NP pairs. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics). Vol. 5. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 395--404."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.03.003"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444421X"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.10.006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/060673886"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.001"},{"key":"e_1_2_1_10_1","series-title":"Lecture Notes in Computer Science","volume-title":"Theoretical Computer Science - Essays in Memory of Shimon Even","author":"Goldreich O.","unstructured":"O. Goldreich . 2006. On promise problems: A survey . In Theoretical Computer Science - Essays in Memory of Shimon Even . Lecture Notes in Computer Science , vol. 3895 , Springer , 254--290. O. Goldreich. 2006. On promise problems: A survey. In Theoretical Computer Science - Essays in Memory of Shimon Even. Lecture Notes in Computer Science, vol. 3895, Springer, 254--290."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217018"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1780"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_29"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1763"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"P. Pudlak. 2001. On reducibility and symmetry of disjoint NP-pairs. Tech. rep. TR01-044 Electronic Colloquium on Computational Complexity.  P. Pudlak. 2001. On reducibility and symmetry of disjoint NP-pairs. Tech. rep. TR01-044 Electronic Colloquium on Computational Complexity.","DOI":"10.1007\/3-540-44683-4_54"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"A. Razborov. 1994. On provably disjoint NP pairs. Tech. rep. TR94-006 Electronic Colloquium on Computational Complexity.  A. Razborov. 1994. On provably disjoint NP pairs. Tech. rep. TR94-006 Electronic Colloquium on Computational Complexity.","DOI":"10.7146\/brics.v1i36.21607"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/070702680"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217062"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591508","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2591508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:30Z","timestamp":1750230090000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["10.1145\/2591508"],"URL":"https:\/\/doi.org\/10.1145\/2591508","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2014,3]]},"assertion":[{"value":"2013-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}