{"entities":{"Q1401365":{"pageid":1412105,"ns":120,"title":"Item:Q1401365","lastrevid":48155101,"modified":"2026-01-03T19:39:20Z","type":"item","id":"Q1401365","labels":{"en":{"language":"en","value":"Resolution lower bounds for the weak functional pigeonhole principle."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1965373"}},"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":"Q1401365$EFFCBBB7-D703-494C-A42E-50739E531F7E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"023bce6c80727a123d0668f94138ad3f1acd86fa","datavalue":{"value":{"text":"Resolution lower bounds for the weak functional pigeonhole principle.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1401365$131EBB6B-C686-4166-BD94-DFB0C40B7C08","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"61b953bb0e9ce9c1ef4aa30803da74075857f30e","datavalue":{"value":"1050.03039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1401365$B59CAC9E-6800-4A9A-B97A-7ADEA9BA3F36","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8e34f369ccd72261bbbcd486adbf8d06097cc9d4","datavalue":{"value":"10.1016/S0304-3975(02)00453-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1401365$B2F19935-AE65-41D4-9F4D-2E892B009B3A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c0bcfb4eb9a7ab6903b269f394ffde6834d9319","datavalue":{"value":{"entity-type":"item","numeric-id":1370854,"id":"Q1370854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$23E99689-F5EA-4062-80D3-BA1E794E9CDF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$7ECAD4EA-D4E5-4C21-9741-A8E3465C3F10","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7c559667253af6b857a12c847a2fbcea5328ae19","datavalue":{"value":{"time":"+2003-08-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1401365$38AC3E99-17B6-489C-BFE8-8E1295A97106","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"01245b5420984554f9baf0789be1333bdb5d0cdf","datavalue":{"value":"The main result of the paper is that every resolution refutation of the functional version of the pigeonhole principle must have the size \\(\\exp (\\Omega(n/(\\log m)^2))\\), where \\(n\\) is the number of the pigeons and \\(m\\) is the number of holes. This fact implies an \\(\\exp(\\Omega(n^{1/3}))\\) lower bound when the number of pigeons \\(m\\) is arbitrary.   The paper contains an overview of some open problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1401365$F47097A8-9078-4725-AAF9-250B1AD9C96F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1401365$14245A1C-3C0A-4415-A0EA-CA77DD1406E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"10eaeaf8bbf8231bbfc812aab8956e260b5a9f12","datavalue":{"value":"03B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1401365$CD1F85CA-FAAC-46AA-9C29-1A667BE39EF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1401365$0F17EA35-963E-4167-B7C8-C0E57476EC5D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f62a9f45a9db0c127e435baaf5adc0fc0a327873","datavalue":{"value":"1965373","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1401365$560C1A0F-005C-4BE1-8AEE-F796C6B20403","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c9977afeaac4d053aef4e5b5c50df2441a2faf8","datavalue":{"value":"resolution method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1401365$07B10412-18F2-407D-951E-A17428359EC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ee539f3c66b5148353f42975573a39b50c5340f","datavalue":{"value":"complexity of proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1401365$0C68A9D7-A29A-4507-B8E0-4F1326903B05","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"05f3dff3edc7d97b14af7ecb326f488fb3fee31b","datavalue":{"value":{"entity-type":"item","numeric-id":583186,"id":"Q583186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$AE5C7F39-828B-4EB8-8F47-D8ADA3442A07","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":"Q1401365$8965D4AD-5AC0-488B-94CE-4EA77FB10E37","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"50621bbf1c084d93515abb8fb9d0b9bcc1e49ecb","datavalue":{"value":{"entity-type":"item","numeric-id":4651526,"id":"Q4651526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$78046F5F-6D99-4CFB-89FC-28E0F28ECFF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0086f5e874fe7e4f38ea6905507c6d71ae7ad220","datavalue":{"value":{"entity-type":"item","numeric-id":4399249,"id":"Q4399249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$66D9F330-8509-4FD7-9AA5-E80ECEBE1F22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08b529296035947435eb136154e374f9657d895b","datavalue":{"value":{"entity-type":"item","numeric-id":4406287,"id":"Q4406287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$DCA19ABF-2CB4-465E-9041-351E0CD931C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ced15fce0c8018e5dfdcdbe2ed656ec7ef7ed09","datavalue":{"value":{"entity-type":"item","numeric-id":5769706,"id":"Q5769706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$7E2B2CEE-8249-4FD7-8D83-E8ADCADBF9E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c19bada21e08e27b656eb12e6e9fa9312ff6eaa4","datavalue":{"value":{"entity-type":"item","numeric-id":4218929,"id":"Q4218929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$B02ED14C-62DF-4116-9AEC-42E353B523FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5035ead90ebf2e92af4cb88fdfc91c7dfa88c06a","datavalue":{"value":{"entity-type":"item","numeric-id":920967,"id":"Q920967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$C65A5B05-E31D-4C9C-9772-C7A9B858E54E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91c636dd583a22faf929d1cb972aae014f779c04","datavalue":{"value":{"entity-type":"item","numeric-id":3496310,"id":"Q3496310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$7CD3BE40-3807-4EAA-9C03-2D73ABF9402B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fc668831a6565a498110f2aeac4eebcb5e83ad5","datavalue":{"value":{"entity-type":"item","numeric-id":4228469,"id":"Q4228469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$0FFD8966-C4FD-44A2-8986-D57988E695BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c0e6b90c16ae5fa1eac19212a306cb84ffec72b","datavalue":{"value":{"entity-type":"item","numeric-id":5613969,"id":"Q5613969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$345301EB-672E-4499-AD3E-4C8786646712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec2fa04d400281f100817ce7e13bdaafd2683670","datavalue":{"value":{"entity-type":"item","numeric-id":1071750,"id":"Q1071750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$E5DC0846-D232-4F09-85EE-11D3DFEE1498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cda1b1ec2ca640f851edde913bce1dc913773603","datavalue":{"value":{"entity-type":"item","numeric-id":4375792,"id":"Q4375792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$36FABE65-875F-471C-8805-322793AA85FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8193d7c4b476fe8a410bad3ae820cd367ab9f75f","datavalue":{"value":{"entity-type":"item","numeric-id":5175989,"id":"Q5175989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$347E0AFC-02F9-49D3-954F-D87CA79861EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2ad3e47c94faa1151c416011d01c8b47211962a","datavalue":{"value":{"entity-type":"item","numeric-id":4818823,"id":"Q4818823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$973A97D0-F784-4883-A244-17CDCEEA6414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14233b39ee81a420329dec23c30f748cd63ce724","datavalue":{"value":{"entity-type":"item","numeric-id":1881260,"id":"Q1881260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$87E1E73B-F334-414E-AC0F-B080E5BF2675","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cca51ed53316b4ad3082264c436bf6f35c32278","datavalue":{"value":{"entity-type":"item","numeric-id":4527043,"id":"Q4527043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$C7858E95-CA60-4621-B489-000B7955E7E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f62ebef9379ad97d2bdc3c2e7f5717f221d056cb","datavalue":{"value":{"entity-type":"item","numeric-id":5514129,"id":"Q5514129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$314D8033-D53C-4630-8930-131E24B10FDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0591701a79dc243f0efc3406b890d83907ab0bce","datavalue":{"value":{"entity-type":"item","numeric-id":5685059,"id":"Q5685059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$A7FB2B24-EDAB-43B4-88E3-BAC5CC8BC0F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"728810277830424bd131e6e77eef399df584ccea","datavalue":{"value":{"entity-type":"item","numeric-id":3780485,"id":"Q3780485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1401365$348A8E83-316C-4920-9C3D-289BCDC57D12","rank":"normal"}],"P1643":[{"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":"3c76119a5d90fbd5bb05030f74b01afe046bb53f","datavalue":{"value":{"amount":"+0.9015541672706604","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":"Q1401365$715432D5-174B-47AB-8097-3B6D9EDF243B","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":"3a8b78aae8aba0a107660728138aefb364023da9","datavalue":{"value":{"amount":"+0.8903951644897461","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":"Q1401365$4CF46F4F-0E5F-45DE-A5CE-C3B2DD4750BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea034fea25af33b206f6d76bb46ef8eb7039dd54","datavalue":{"value":{"entity-type":"item","numeric-id":558246,"id":"Q558246"},"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":"Q1401365$70E1D180-CD18-4CF6-9598-C5B8F4722953","rank":"normal"},{"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":"e6df8d33ebdb30bb9324e74f7aac3b1d1e40148e","datavalue":{"value":{"amount":"+0.8737884163856506","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":"Q1401365$D283C183-7FF0-439A-8BC1-2D8C14ACE19A","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":"4b6b123a6c4b3ee5208001a3af1d81bc0d4b6ce6","datavalue":{"value":{"amount":"+0.8511380553245544","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":"Q1401365$5CF43AE4-6C9E-4852-9D40-3C153297DAC0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1401365","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1401365"}}}}}