{"entities":{"Q558246":{"pageid":560013,"ns":120,"title":"Item:Q558246","lastrevid":48511354,"modified":"2026-01-05T01:39:13Z","type":"item","id":"Q558246","labels":{"en":{"language":"en","value":"Regular resolution lower bounds for the weak pigeonhole principle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2186328"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558246$A1948BF8-5D41-420F-A36F-0AF2DCCE63D2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a40f563b4219add285eaa39d21e61e826ff83d3a","datavalue":{"value":{"text":"Regular resolution lower bounds for the weak pigeonhole principle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q558246$E7448704-2CB1-490D-A49D-3C9A571142D5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"98e552d61525e4e60b11a73be286392195a66c4b","datavalue":{"value":"1063.03044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558246$4EB8A761-A610-400F-AF0C-D317081F08A8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38b40ed6cb099fba5da493703b11839c0af89042","datavalue":{"value":{"entity-type":"item","numeric-id":202089,"id":"Q202089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558246$99878259-C9AB-4C70-A0E1-DEA1E9F5B94C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b481d9d1e1fd6339de38d10a65dabc0f21090cc0","datavalue":{"value":{"entity-type":"item","numeric-id":168589,"id":"Q168589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558246$3438A265-17BF-4656-BE11-547E8BE8C813","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558246$FA5739B3-C7D6-4315-BD95-83203F2A9AB6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4ec6781aaf52ba28014d9ade37521fee8bad32d","datavalue":{"value":{"time":"+2005-07-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q558246$FE5A3E78-BEA6-49BA-9494-45A700374C94","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"03ebcb46e7a94b3dbe2e8147b9040693e6c81bf2","datavalue":{"value":"The paper is devoted to the study of the complexity of resolution proofs of the weak pigeonhole principle WPHP. It is shown that for any \\(m\\), any regular resolution proof for WPHP\\(^{m}_{n}\\) (i.e., weak pigeonhole principle with \\(m\\) pigeons and \\(n\\) holes) is of length \\(\\Omega (2^{n^{\\epsilon}})\\), where \\(\\epsilon > 0\\) is some global constant.","type":"string"},"datatype":"string"},"type":"statement","id":"Q558246$EBD71C08-B44C-4158-883E-5FF19ED874AE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c45938d3b1c1a5c68183caabb02f42934d9ff682","datavalue":{"value":{"entity-type":"item","numeric-id":588140,"id":"Q588140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558246$CBE2969B-91BE-4613-A518-534976AA75F4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558246$A40B00BD-3A28-4F03-9EB2-E867E1FF9395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558246$573568DB-CD26-41D7-91EA-09B028D310CD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d15cb923a0c98133a34533eda8e7e4a2510c2906","datavalue":{"value":"2186328","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558246$A64C40B1-F2F4-478C-9541-8B1C5FBFBAB6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c5d788dff212a5ac668b31d3f2ad47b96140a66","datavalue":{"value":"weak pigeonhole principle","type":"string"},"datatype":"string"},"type":"statement","id":"Q558246$272DC3D1-891C-4256-8366-0BECD0FB087E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9006d2cf0c261025e0da61cd1f14ea83b5c4ae4f","datavalue":{"value":"complexity of resolution proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q558246$CFD644B3-7283-4505-B429-0BCAD3FB07FE","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558246$2A3C0698-00B3-4680-A482-0242A100645F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b9f4756eed469cf87d54732481f048336e7e34b8","datavalue":{"value":"https://doi.org/10.1007/s00493-004-0029-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q558246$8CBF210C-E500-47C4-A712-9785420C3A9F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"13a55e22ce27970e89d63d734ba7dcb17a1d8ccf","datavalue":{"value":"W2001378190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558246$05D4F4D3-095B-41A7-A099-CEEBE5B3C8B3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d0860d15198eb5741dd76c51411281e8730281ec","datavalue":{"value":"10.1007/S00493-004-0029-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558246$0BE0F8ED-7DEA-4ABC-9D61-0FDC424F37DE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc926d34953ac6340be0c23a4ae8361ba53ea0c5","datavalue":{"value":{"entity-type":"item","numeric-id":5175989,"id":"Q5175989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b6e01267eb8a044ff1e65265285a3de3e024715","datavalue":{"value":{"amount":"+0.9561362862586976","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q558246$94C7DD7F-763F-417D-A1B8-C6E00AEDB732","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80adba55132ad81c69da414cbebaa257ccfb28de","datavalue":{"value":{"entity-type":"item","numeric-id":5501187,"id":"Q5501187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0db88a5688a1e621f9875b1c72bb21a14e71b11f","datavalue":{"value":{"amount":"+0.9056614637374878","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q558246$8D819542-01BE-4F89-9289-2F5ADECB520C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69cf90495e95ccafed6b110166466fb6ca23310d","datavalue":{"value":{"entity-type":"item","numeric-id":1401365,"id":"Q1401365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ee3c9faf533903ccf92e78a94b1c9e5ac47b188","datavalue":{"value":{"amount":"+0.8739801049232483","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q558246$46DB7DB4-0740-4C33-99D2-A8A3577014B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e0247af87e176aafad6848ca6c4df8650b0e491","datavalue":{"value":{"entity-type":"item","numeric-id":920967,"id":"Q920967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"404e0d3adff5b792f6d78b3a0b9c57320e978b07","datavalue":{"value":{"amount":"+0.8654825091362","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q558246$3B28EE47-DD32-46B2-A078-015E9604643D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a313ae0355a151e08b3e949539235d6f5e8d4fa","datavalue":{"value":{"entity-type":"item","numeric-id":4218929,"id":"Q4218929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38764e8d1772b5722fb610d5b813c31634c67dd3","datavalue":{"value":{"amount":"+0.8647990226745605","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q558246$AE6F4CAE-31A0-4E04-8102-E0F45692B79E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:558246","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:558246"}}}}}