{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:22:09Z","timestamp":1737091329456,"version":"3.33.0"},"reference-count":17,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3603,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1997,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a simple and completely model\u2010theoretical proof of a strengthening of a theorem of Ajtai: The independence of the pigeonhole principle from<jats:italic>I<\/jats:italic>\u0394<jats:sub>0<\/jats:sub>(<jats:italic>R<\/jats:italic>). With regard to strength, the theorem proved here corresponds to the complexity\/proof\u2010theoretical results of [10] and [14], but a different combinatorics is used. Techniques inspired by Razborov [11] replace those derived from H\u00e5stad [8]. This leads to a much shorter and very direct construction.<\/jats:p>","DOI":"10.1002\/malq.19970430313","type":"journal-article","created":{"date-parts":[[2007,5,29]],"date-time":"2007-05-29T15:34:47Z","timestamp":1180452887000},"page":"401-412","source":"Crossref","is-referenced-by-count":2,"title":["Forcing in Finite Structures"],"prefix":"10.1002","volume":"43","author":[{"given":"Domenico","family":"Zambella","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"Ajtai M. The complexity of the pigeonhole principle. Proceedings 29th IEEE Annual Symposium on Foundations of Computer Science1988 346\u2013355.","DOI":"10.1109\/SFCS.1988.21951"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-3466-1_1"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"Ajtai M. The independence of the modulo p counting principles. Proceedings 26th Annual AMC Symposium on Theory of Computing1985 402\u2013411.","DOI":"10.1145\/195058.195207"},{"key":"e_1_2_1_6_2","unstructured":"Beame P. A switching lemma primer. Unpublished notes."},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"Cook S. A. Feasibly constructive proofs and the propositional calculus. Proceedings 7th Annual AMC Symposium on Theory of Computing1975 83\u201397.","DOI":"10.1145\/800116.803756"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"Furst M. J. B.Saxe andM.Sipser Parity circuits and the polynomial time hierarchy. Proceedings 22th IEEE Annual Symposium on Foundations of Computer Science1981 260\u2013270.","DOI":"10.1109\/SFCS.1981.35"},{"key":"e_1_2_1_9_2","first-page":"143","volume-title":"Randomness and Computation","author":"H\u00e5stad J.","year":"1989"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"key":"e_1_2_1_11_2","first-page":"15","volume-title":"Random Structures and Algorithms","author":"Kraj\u00ed\u010dek J.","year":"1995"},{"key":"e_1_2_1_12_2","first-page":"344","volume-title":"Feasible Mathematics II","author":"Razborov A. A.","year":"1993"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0075316"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-127-1-67-76"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200117"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"Riis S. Count(p) does not imply Count(q). BRICS\u2010preprint RS\u201094\u201021 1995 http:\/\/www.brics.aau.dk\/BRICS\/.","DOI":"10.7146\/brics.v1i21.21646"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"Yao A. C. Separating the polynomial\u2010time hierarchy by oracles. Proceedings 26th IEEE Annual Symposium on Foundations of Computer Science 1985 1\u201310.","DOI":"10.1109\/SFCS.1985.49"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.2307\/2275794"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19970430313","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19970430313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T18:56:10Z","timestamp":1737053770000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19970430313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["10.1002\/malq.19970430313"],"URL":"https:\/\/doi.org\/10.1002\/malq.19970430313","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}