{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:23Z","timestamp":1760202563448},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_54","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"621-632","source":"Crossref","is-referenced-by-count":13,"title":["On Reducibility and Symmetry of Disjoint NP-Pairs"],"prefix":"10.1007","author":[{"given":"Pavel","family":"Pudl\u00e1k","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"54_CR1","unstructured":"M. Alekhnovich and A. A. Razborov, Resolution is Not Automatizable Unless W[P] is Tractable, http:\/\/genesis.mi.ras.ru\/~razborov\/ ."},{"issue":"3","key":"54_CR2","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930050058","volume":"19","author":"L. Babai","year":"1999","unstructured":"L. Babai, A. G\u00e1l and A. Wigderson, Superpolynomial lower bounds for monotone span programs, Combinatorica 19(3), 1999, 301\u2013319.","journal-title":"Combinatorica"},{"issue":"6","key":"54_CR3","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1137\/S0097539798353230","volume":"29","author":"M. Bonet","year":"2000","unstructured":"M. Bonet, T. Pitassi and R. Raz, On interpolation and automatization for Frege systems. SIAM J. on Computing 29(6), (2000), 1939\u20131967.","journal-title":"SIAM J. on Computing"},{"key":"54_CR4","first-page":"326","volume":"58","author":"S. A. Cook","year":"1999","unstructured":"S. A. Cook and A. Haken, An exponential lower bound for the size of monotone real circuits, JCSS 58, (1999), 326\u2013335.","journal-title":"JCSS"},{"key":"54_CR5","doi-asserted-by":"crossref","unstructured":"S. A. Cook and Reckhow, The relative efficiency of propositional proof systems, J. of Symbolic Logic, 44(1), 36\u201350.","DOI":"10.2307\/2273702"},{"key":"54_CR6","doi-asserted-by":"crossref","unstructured":"J. Kraj\u00ed\u010dek, Bounded arithmetic, propositional logic, and complexity theory, Cambridge Univ. Press, 1995.","DOI":"10.1017\/CBO9780511529948"},{"key":"54_CR7","doi-asserted-by":"crossref","unstructured":"J. Kraj\u00ed\u010dek and P. Pudl\u00e1k, Propositional proof systems, the consistency of first order theories and the complexity of computations, J. of Symbolic Logic, 54(3), 1063\u20131079.","DOI":"10.2307\/2274765"},{"key":"54_CR8","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/inco.1997.2674","volume":"142","author":"J. Kraj\u00ed\u010dek","year":"1998","unstructured":"J. Kraj\u00ed\u010dek and P. Pudl\u00e1k, Some consequences of cryptographical conjectures for S2 1 and EF. Information and Computation 142, (1998), 82\u201394","journal-title":"Information and Computation"},{"key":"54_CR9","unstructured":"L. Ku\u010dera, Cryptography and random graphs, preprint."},{"key":"54_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz, On the Shannon capacity of graphs, IEEE Trans. Inform. Theory 25, 1979, 1\u20137.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"54_CR11","first-page":"197","volume":"97","author":"P. Pudl\u00e1k","year":"1999","unstructured":"P. Pudl\u00e1k, On the complexity of propositional calculus, Sets and Proofs, Invited papers from Logic Colloquium\u201997, Cambridge Univ. Press, 1999, 197\u2013218.","journal-title":"Invited papers from Logic Colloquium\u2019"},{"key":"54_CR12","unstructured":"A. A. Razborov, Lower bounds on the monotone complexity of some Boolean functions, Soviet Mathem. Doklady 31, 354\u2013357."},{"key":"54_CR13","doi-asserted-by":"crossref","unstructured":"A. A. Razborov, On provably disjoint NP-pairs, BRICS Report Series RS-94-36, 1994, http:\/\/www.brics.dk\/RS\/94\/36\/index.html .","DOI":"10.7146\/brics.v1i36.21607"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:27:50Z","timestamp":1556818070000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_54","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}