{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T07:53:55Z","timestamp":1720770835267},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2004,3]]},"abstract":"\n We prove that any Resolution proof for the weak pigeonhole principle, with\n n<\/jats:italic>\n holes and any number of pigeons, is of length \u03a9(2\n \n n<\/jats:italic>\n \u03f5<\/jats:sup>\n <\/jats:sup>\n ), (for some global constant \u03f5 > 0). One corollary is that a certain propositional formulation of the statement\n NP<\/jats:italic>\n \u2284\n P<\/jats:italic>\n \/\n poly<\/jats:italic>\n does not have short Resolution proofs.\n <\/jats:p>","DOI":"10.1145\/972639.972640","type":"journal-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T16:39:33Z","timestamp":1090341573000},"page":"115-138","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Resolution lower bounds for the weak pigeonhole principle"],"prefix":"10.1145","volume":"51","author":[{"given":"Ran","family":"Raz","sequence":"first","affiliation":[{"name":"Weizmann Institute, Rehovot, Israel"}]}],"member":"320","published-online":{"date-parts":[[2004,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Alon N. Spencer J. and Erdos P. 1992. The Probabiliatic Method. Wiley New York. Alon N. Spencer J. and Erdos P. 1992. The Probabiliatic Method. Wiley New York."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 274--282","author":"Beame P."},{"key":"e_1_2_1_3_1","unstructured":"Beame P. and Pitassi T. 2001. Propositional proof complexity: Past present and future. In Current Trends in Theoretical Computer Science. 42--70. Beame P. and Pitassi T. 2001. Propositional proof complexity: Past present and future. In Current Trends in Theoretical Computer Science. 42--70."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_2_1_5_1","volume-title":"Lecture Notes in Computer Science","volume":"1414","author":"Buss S."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90072-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380821"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Pudlak P. 2000. Proofs as games. Amer. Math. Month 541--550. Pudlak P. 2000. Proofs as games. Amer. Math. Month 541--550.","DOI":"10.1080\/00029890.2000.12005233"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509987"},{"key":"e_1_2_1_12_1","first-page":"344","article-title":"Bounded arithmetic and lower bounds in boolean complexity","volume":"13","author":"Razborov A.","year":"1995","journal-title":"Feas. Math. II. Prog. Comput. Sci. Appl. Logic"},{"key":"e_1_2_1_13_1","volume-title":"Lecture Notes in Computer Science","volume":"1099","author":"Razborov A.","year":"1996"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050013"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Razborov A. 2001b. Proof complexity of pigeonhole principles. In Developments in Language Theory. 100--116. Razborov A. 2001b. Proof complexity of pigeonhole principles. In Developments in Language Theory. 100--116.","DOI":"10.1007\/3-540-46011-X_8"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873163"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258673"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.8928"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/972639.972640","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T07:47:52Z","timestamp":1672732072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/972639.972640"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,3]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,3]]}},"alternative-id":["10.1145\/972639.972640"],"URL":"https:\/\/doi.org\/10.1145\/972639.972640","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,3]]},"assertion":[{"value":"2004-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}