{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:15:29Z","timestamp":1750306529780,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,12,9]],"date-time":"2014-12-09T00:00:00Z","timestamp":1418083200000},"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,12,9]]},"abstract":"<jats:p>This article surveys results on disjoint NP-pairs, propositional proof systems, function classes, and promise classes|including results that demonstrate close connections that bind these topics together. We illustrate important links between the questions of whether these classes have complete objects and whether optimal proof systems may exist.<\/jats:p>","DOI":"10.1145\/2696081.2696095","type":"journal-article","created":{"date-parts":[[2014,12,16]],"date-time":"2014-12-16T13:39:54Z","timestamp":1418737194000},"page":"59-75","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Disjoint NP-Pairs and Propositional Proof Systems"],"prefix":"10.1145","volume":"45","author":[{"given":"C.","family":"Gla\u00dfer","sequence":"first","affiliation":[{"name":"University at W\u00fcrzburg, Germany"}]},{"given":"A.","family":"Hughes","sequence":"additional","affiliation":[{"name":"University at Buffalo, New York"}]},{"given":"A. L.","family":"Selman","sequence":"additional","affiliation":[{"name":"University at Buffalo, New York"}]},{"given":"N.","family":"Wisiol","sequence":"additional","affiliation":[{"name":"University at Buffalo, New York"}]}],"member":"320","published-online":{"date-parts":[[2014,12,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"H.\n      Buhrman S. A.\n      Fenner L.\n      Fortnow and \n      D.\n      van Melkebeek\n    .\n  Optimal proof systems and sparse sets\n  . In Horst Reichel and Sophie Tison editors STACS volume \n  1770\n   of \n  Lecture Notes in Computer Science pages \n  407\n  --\n  418\n  . \n  Springer 2000\n  .   H. Buhrman S. A. Fenner L. Fortnow and D. van Melkebeek. Optimal proof systems and sparse sets. In Horst Reichel and Sophie Tison editors STACS volume 1770 of Lecture Notes in Computer Science pages 407--418. Springer 2000.","DOI":"10.1007\/3-540-46541-3_34"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210008"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213030"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.01.002"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80056-X"},{"key":"e_1_2_1_8_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/11685654_12","volume-title":"Essays in Memory of Shimon Even","author":"Goldreich O.","year":"2006","unstructured":"O. Goldreich . On promise problems: A survey . In O. Goldreich, A. L. Rosenberg, and A. L. Selman, editors, Essays in Memory of Shimon Even , volume 3895 of Lecture Notes in Computer Science , pages 254 -- 290 . Springer , 2006 . O. Goldreich. On promise problems: A survey. In O. Goldreich, A. L. Rosenberg, and A. L. Selman, editors, Essays in Memory of Shimon Even, volume 3895 of Lecture Notes in Computer Science, pages 254--290. Springer, 2006."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217018"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.03.003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703425848"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.10.006"},{"issue":"1","key":"e_1_2_1_13_1","first-page":"34","article-title":"Relativizing function classes","volume":"9","author":"Gla\u00dfer C.","year":"2003","unstructured":"C. Gla\u00dfer and G. Wechsung . Relativizing function classes . J. UCS , 9 ( 1 ): 34 -- 50 , 2003 . C. Gla\u00dfer and G. Wechsung. Relativizing function classes. J. UCS, 9(1):34--50, 2003.","journal-title":"J. UCS"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90022-9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/646239.683504"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268315"},{"key":"e_1_2_1_17_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/978-3-642-31594-7_40","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Hughes A.","year":"2012","unstructured":"A. Hughes , A. Pavan , N. Russell , and A. L. Selman . A thirty year old conjecture about promise problems . In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, International Colloquium on Automata, Languages, and Programming , volume 7391 of Lecture Notes in Computer Science , pages 473 -- 484 . Springer , 2012 . 10.1007\/978-3-642-31594-7_40 A. Hughes, A. Pavan, N. Russell, and A. L. Selman. A thirty year old conjecture about promise problems. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, International Colloquium on Automata, Languages, and Programming, volume 7391 of Lecture Notes in Computer Science, pages 473--484. Springer, 2012. 10.1007\/978-3-642-31594-7_40"},{"key":"e_1_2_1_18_1","series-title":"Koninklijke Nederlandse Akademie van Wetenschappen","first-page":"800","volume-title":"Proceedings of the section of sciences","author":"Kleene S. C.","year":"1950","unstructured":"S. C. Kleene . A symmetric form of G\u00f6del's theorem . In Proceedings of the section of sciences , volume 12 of Koninklijke Nederlandse Akademie van Wetenschappen , pages 800 -- 802 . Springer Verlag , 1950 . S. C. Kleene. A symmetric form of G\u00f6del's theorem. In Proceedings of the section of sciences, volume 12 of Koninklijke Nederlandse Akademie van Wetenschappen, pages 800--802. Springer Verlag, 1950."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"J.\n      K\u00f6bler\n     and \n      J.\n      Me\u00dfner\n  . \n  Is the standard proof system for SAT P-optimal? In Sanjiv Kapoor and Sanjiva Prasad editors Foundations of Software Technology and Theoretical Computer Science (FSTTCS) volume \n  1974\n   of \n  Lecture Notes in Computer Science pages \n  361\n  --\n  372\n  . \n  Springer 2000\n  .   J. K\u00f6bler and J. Me\u00dfner. Is the standard proof system for SAT P-optimal? In Sanjiv Kapoor and Sanjiva Prasad editors Foundations of Software Technology and Theoretical Computer Science (FSTTCS) volume 1974 of Lecture Notes in Computer Science pages 361--372. Springer 2000.","DOI":"10.1007\/3-540-44450-5_29"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00058-0"},{"key":"e_1_2_1_21_1","first-page":"364","volume-title":"Proceedings of the 11th Symposium on Mathematical Foundations of Computer Science","author":"Kowalczyk W.","year":"1984","unstructured":"W. Kowalczyk . Some connections between representability of complexity classes and the power of formal reasoning systems . In Proceedings of the 11th Symposium on Mathematical Foundations of Computer Science , pages 364 -- 369 . Springer-Verlag Lecture Notes in Computer Science #176 , 1984 . W. Kowalczyk. Some connections between representability of complexity classes and the power of formal reasoning systems. In Proceedings of the 11th Symposium on Mathematical Foundations of Computer Science, pages 364--369. Springer-Verlag Lecture Notes in Computer Science #176, 1984."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274765"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_2_1_25_1","volume-title":"Gauthier- Villars","author":"Luzin N. N.","year":"1930","unstructured":"N. N. Luzin . Le\u00e7ons sur les ensembles analytiques et leurs applications . Gauthier- Villars , 1930 . N. N. Luzin. Le\u00e7ons sur les ensembles analytiques et leurs applications. Gauthier- Villars, 1930."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00060-7"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00411-5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322306"},{"key":"e_1_2_1_29_1","volume-title":"On provably disjoint NP-pairs. Electronic Colloquium on Computational Complexity (ECCC), 1(6)","author":"Razborov A. A.","year":"1994","unstructured":"A. A. Razborov . On provably disjoint NP-pairs. Electronic Colloquium on Computational Complexity (ECCC), 1(6) , 1994 . A. A. Razborov. On provably disjoint NP-pairs. Electronic Colloquium on Computational Complexity (ECCC), 1(6), 1994."},{"key":"e_1_2_1_30_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/3-540-12689-9_119","volume-title":"Proceedings Foundations of Computation Theory","author":"Regan K.","year":"1983","unstructured":"K. Regan . On diagonalization methods and the structure of language classes . In Proceedings Foundations of Computation Theory , volume 158 of Lecture Notes in Computer Science , pages 368 -- 380 . Springer Verlag , 1983 . K. Regan. On diagonalization methods and the structure of language classes. In Proceedings Foundations of Computation Theory, volume 158 of Lecture Notes in Computer Science, pages 368--380. Springer Verlag, 1983."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90036-0"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321253"},{"key":"e_1_2_1_33_1","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Jr H. Rogers","year":"1967","unstructured":"H. Rogers Jr . Theory of Recursive Functions and Effective Computability . McGraw-Hill , New York , 1967 . H. Rogers Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90114-1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80009-1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.2307\/2964013"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2307\/2964680"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/646236.682721"},{"key":"e_1_2_1_39_1","first-page":"143","article-title":"Undecidability and recursive inseparability. Zeitschr. f. math. Logik und Grundlagen d","volume":"4","author":"Smullyan R. M.","year":"1958","unstructured":"R. M. Smullyan . Undecidability and recursive inseparability. Zeitschr. f. math. Logik und Grundlagen d . Math. , 4 : 143 -- 147 , 1958 . R. M. Smullyan. Undecidability and recursive inseparability. Zeitschr. f. math. Logik und Grundlagen d. Math., 4:143--147, 1958.","journal-title":"Math."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122563"},{"key":"e_1_2_1_41_1","first-page":"953","article-title":"On recursive separability","volume":"88","author":"Trakhtenbrot B.","year":"1953","unstructured":"B. Trakhtenbrot . On recursive separability . Dokl. Akad. Nauk SSSR , 88 : 953 -- 955 , 1953 . B. Trakhtenbrot. On recursive separability. Dokl. Akad. Nauk SSSR, 88:953--955, 1953.","journal-title":"Dokl. Akad. Nauk SSSR"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2696081.2696095","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2696081.2696095","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:11Z","timestamp":1750227131000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2696081.2696095"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,9]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12,9]]}},"alternative-id":["10.1145\/2696081.2696095"],"URL":"https:\/\/doi.org\/10.1145\/2696081.2696095","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2014,12,9]]},"assertion":[{"value":"2014-12-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}