{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:01Z","timestamp":1750694701974},"reference-count":34,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2011,6,16]],"date-time":"2011-06-16T00:00:00Z","timestamp":1308182400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1"},{"start":{"date-parts":[[2011,6,16]],"date-time":"2011-06-16T00:00:00Z","timestamp":1308182400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Quarterly"],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1002\/malq.201010021","type":"journal-article","created":{"date-parts":[[2011,6,17]],"date-time":"2011-06-17T03:33:44Z","timestamp":1308281624000},"page":"535-550","source":"Crossref","is-referenced-by-count":4,"title":["Do there exist complete sets for promise classes?"],"prefix":"10.1002","volume":"57","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[]},{"given":"Zenon","family":"Sadowski","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2011,6,16]]},"reference":[{"key":"10.1002\/malq.201010021-BIB1|cit1","volume-title":"Structural Complexity I, EATCS Monographs on Theoretical Computer Science Vol. 11","author":"Balc\u00e1zar","year":"1988"},{"issue":"1-3","key":"10.1002\/malq.201010021-BIB2|cit2","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.tcs.2007.02.005","article-title":"Classes of representable disjoint NP-pairs","volume":"377","author":"Beyersdorff","year":"2007","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10.1002\/malq.201010021-BIB3|cit3","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/s00224-007-9023-8","article-title":"Tuples of disjoint NP-sets","volume":"43","author":"Beyersdorff","year":"2008","journal-title":"Theory Comput. Syst."},{"key":"10.1002\/malq.201010021-BIB4|cit4","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1109\/SYNASC.2009.9","volume-title":"SYNASC 2009, Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing","author":"Beyersdorff","year":"2009"},{"issue":"3","key":"10.1002\/malq.201010021-BIB5|cit5","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/j.ic.2010.11.006","article-title":"Proof systems that take advice","volume":"209","author":"Beyersdorff","year":"2011","journal-title":"Inf. Comput."},{"issue":"38-40","key":"10.1002\/malq.201010021-BIB6|cit6","doi-asserted-by":"crossref","first-page":"3839","DOI":"10.1016\/j.tcs.2009.05.021","article-title":"Nondeterministic functions and the existence of optimal proof systems","volume":"410","author":"Beyersdorff","year":"2009","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10.1002\/malq.201010021-BIB7|cit7","article-title":"A tight Karp-Lipton collapse result in bounded arithmetic","volume":"11","author":"Beyersdorff","year":"2010","journal-title":"ACM Tr. Comput. Log."},{"key":"10.1002\/malq.201010021-BIB8|cit8","first-page":"47","volume-title":"Computer Science-Theory and Applications, Proceedings of the 4th International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009","author":"Beyersdorff","year":"2009"},{"key":"10.1002\/malq.201010021-BIB9|cit9","first-page":"321","volume-title":"Automata, Languages and Programming, Proceedings of the 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010","author":"Chen","year":"2010"},{"issue":"4","key":"10.1002\/malq.201010021-BIB10|cit10","doi-asserted-by":"crossref","first-page":"1353","DOI":"10.2178\/jsl\/1203350791","article-title":"Consequences of the provability of NP \u2286 P\/poly","volume":"72","author":"Cook","year":"2007","journal-title":"J. Symb. Log."},{"key":"10.1002\/malq.201010021-BIB11|cit11","first-page":"83","volume-title":"Proceedings of the 7th Annual ACM Symposium on Theory of Computing","author":"Cook","year":"1975"},{"issue":"1","key":"10.1002\/malq.201010021-BIB12|cit12","doi-asserted-by":"crossref","first-page":"36","DOI":"10.2307\/2273702","article-title":"The relative efficiency of propositional proof systems","volume":"44","author":"Cook","year":"1979","journal-title":"J. Symb. Log."},{"issue":"2","key":"10.1002\/malq.201010021-BIB13|cit13","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/j.ic.2005.03.003","article-title":"Reductions between disjoint NP-pairs","volume":"200","author":"Gla\u00dfer","year":"2005","journal-title":"Inf. Comput."},{"issue":"6","key":"10.1002\/malq.201010021-BIB14|cit14","doi-asserted-by":"crossref","first-page":"1369","DOI":"10.1137\/S0097539703425848","article-title":"Disjoint NP-pairs","volume":"33","author":"Gla\u00dfer","year":"2004","journal-title":"SIAM J. Comput."},{"key":"10.1002\/malq.201010021-BIB15|cit15","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/11685654_11","volume-title":"Essays in Theoretical Computer Science in Memory of Shimon Even","author":"Gla\u00dfer","year":"2006"},{"issue":"1-3","key":"10.1002\/malq.201010021-BIB16|cit16","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.tcs.2006.10.006","article-title":"Canonical disjoint NP-pairs of propositional proof systems","volume":"370","author":"Gla\u00dfer","year":"2007","journal-title":"Theor. Comput. Sci."},{"key":"10.1002\/malq.201010021-BIB17|cit17","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","article-title":"Complexity classes without machines: On complete languages for UP","volume":"58","author":"Hartmanis","year":"1988","journal-title":"Theor. Comput. Sci."},{"key":"10.1002\/malq.201010021-BIB18|cit18","first-page":"453","volume-title":"Leibniz International Proceedings in Informatics Vol. 5","author":"Hirsch","year":"2010"},{"key":"10.1002\/malq.201010021-BIB19|cit19","first-page":"28","volume-title":"Lecture Notes in Computer Science Vol. 6108","author":"Hirsch","year":"2010"},{"key":"10.1002\/malq.201010021-BIB20|cit20","first-page":"155","volume-title":"Computer Science-Theory and Applications, Proceedings of the 4th International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009","author":"Itsykson","year":"2009"},{"key":"10.1002\/malq.201010021-BIB21|cit21","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/0022-0000(89)90024-X","article-title":"PNP[log n] and sparse Turing-complete sets for NP","volume":"39","author":"Kadin","year":"1989","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10.1002\/malq.201010021-BIB22|cit22","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0890-5401(03)00058-0","article-title":"Optimal proof systems imply complete sets for promise classes","volume":"184","author":"K\u00f6bler","year":"2003","journal-title":"Inf. Comput."},{"key":"10.1002\/malq.201010021-BIB23|cit23","first-page":"364","volume-title":"Mathematical Foundations of Computer Science 1984, Praha, Czechoslovakia, September 1984","author":"Kowalczyk","year":"1984"},{"issue":"3","key":"10.1002\/malq.201010021-BIB24|cit24","first-page":"1063","article-title":"Propositional proof systems","volume":"54","author":"Kraj\u00ed\u010dek","year":"1989","journal-title":"the consistency of first order theories and the complexity of computations, J. Symb. Log."},{"issue":"1","key":"10.1002\/malq.201010021-BIB25|cit25","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1006\/inco.1997.2674","article-title":"Some consequences of cryptographical conjectures for S12 and EF","volume":"140","author":"Kraj\u00ed\u010dek","year":"1998","journal-title":"Inf. Comput."},{"key":"10.1002\/malq.201010021-BIB26|cit26","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1137\/0214003","article-title":"On circuit-size complexity and the low hierarchy in NP","volume":"14","author":"Ko","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1002\/malq.201010021-BIB27|cit27","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The Graph Isomorphism Problem: Its Structural Complexity, Progress in Theoretical Computer Science","author":"K\u00f6bler","year":"1993"},{"key":"10.1002\/malq.201010021-BIB28|cit28","first-page":"370","volume-title":"Proceedings of the Innovations in Computer Science, ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010","author":"Pitassi","year":"2010"},{"key":"10.1002\/malq.201010021-BIB29|cit29","first-page":"423","volume-title":"Fundamentals of Computation Theory, Proceedings of the 11th International Symposium, FCT '97, Krak\u00f3w, Poland, September 1-3, 1997","author":"Sadowski","year":"1997"},{"issue":"1","key":"10.1002\/malq.201010021-BIB30|cit30","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0304-3975(01)00155-4","article-title":"On an optimal propositional proof system and the structure of easy subsets of TAUT","volume":"288","author":"Sadowski","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"10.1002\/malq.201010021-BIB31|cit31","first-page":"407","volume-title":"Logic and Theory of Algorithms, Fourth Conference on Computability in Europe, CiE 2008, Local Proceedings","author":"Sadowski","year":"2010"},{"key":"10.1002\/malq.201010021-BIB32|cit32","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","article-title":"A low and a high hierarchy within NP","volume":"27","author":"Sch\u00f6ning","year":"1983","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10.1002\/malq.201010021-BIB33|cit33","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/S0022-0000(05)80009-1","article-title":"A taxonomy of complexity classes of functions","volume":"48","author":"Selman","year":"1994","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1002\/malq.201010021-BIB34|cit34","first-page":"198","volume-title":"Much ado about functions, in: Proceedings of the 11th Annual IEEE Conference on Computational Complexity","author":"Selman","year":"1996"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.201010021","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.201010021","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full\/10.1002\/malq.201010021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,3]],"date-time":"2021-07-03T13:30:05Z","timestamp":1625319005000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.201010021"}},"subtitle":["Do there exist complete sets for promise classes?"],"short-title":[],"issued":{"date-parts":[[2011,6,16]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,12]]}},"URL":"https:\/\/doi.org\/10.1002\/malq.201010021","archive":["Portico"],"relation":{},"ISSN":["0942-5616"],"issn-type":[{"value":"0942-5616","type":"print"}],"subject":[],"published":{"date-parts":[[2011,6,16]]}}}