{"entities":{"Q1121017":{"pageid":1131766,"ns":120,"title":"Item:Q1121017","lastrevid":66172746,"modified":"2026-04-12T08:02:02Z","type":"item","id":"Q1121017","labels":{"en":{"language":"en","value":"On Ne\u010diporuk's theorem for branching programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4102486"}},"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":"Q1121017$E103BFA6-129B-40AF-97E4-210FE6A0041D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e84192b378f31851e007e8b79cb09dd40dffc35e","datavalue":{"value":{"text":"On Ne\u010diporuk's theorem for branching programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1121017$768DBD80-F86A-4D41-92AD-2DF31D13E4D2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"46bffd713fd61c617835073ef18a2159b0b743ff","datavalue":{"value":"0673.68027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121017$2F7219E1-C168-45F9-8802-AB660A561B92","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2451aea490f691ac580997a15270676ae54a86e0","datavalue":{"value":"10.1016/0304-3975(89)90054-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121017$D7457756-600C-4975-B910-FF39674AD8FB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"da68626a0a4efbe01f8daa4dbbed98fdea696571","datavalue":{"value":{"entity-type":"item","numeric-id":233001,"id":"Q233001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121017$A4CF201D-003C-40BC-A882-5FA80F86901C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121017$69F6FFB4-5279-44AD-8347-57F093E76BA7","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":"Q1121017$EACDED5B-DB5E-4729-B4B1-FB8FA3EEC02A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1121017$6DCAAD32-A0F1-47BC-BABD-115C481A9D4C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3d8be9cd3fd8f4e735dde8866a1ba9a7fa8eaa8d","datavalue":{"value":"In 1966 Ne\u010diporuk derived the following lower bound for the minimal size BP(f) of a branching program which computes the Boolean function f: \\(BP(f)=\\Omega (\\sum^{p}_{i=1}(\\log r_ i(f))/(\\log \\log r_ i(f)))\\) where \\(V_ 1,...,V_ p\\) is a partition of the set of variables of f and \\(r_ i(f)\\) denotes the number of different restrictions of f to \\(V_ i.\\)    Alon and Zwick determine the largest monotone nondecreasing function t for which Ne\u010diporuk's theorem remains true if the above sum is replaced by \\(\\sum^{p}_{i=1}t(r_ i(f))\\). They show t(m)\\(\\sim (1/2)(\\log m)/(\\log \\log m)\\) and derive an explicit formulae for t.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121017$21C1C1AA-853D-48CE-A062-208BC996ACE7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121017$612EA066-B3F5-4C80-9184-F5766996D6DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121017$2BF59706-A031-4EE2-AE27-2B145A8B1C82","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a7f1843e73199b4fcf7f675eac86ec782012829a","datavalue":{"value":"4102486","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121017$94579BB8-7349-4799-8904-EB1D716E0DBE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121017$337AC505-3655-4AF3-BCE7-9759C7A2AE61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bf1c8d33f6fc76ac2e221ea69999b4912603564","datavalue":{"value":"branching program","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121017$0CEDE331-D01F-4D34-AF3D-B25135DE3E94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"045553e3e8d91b8a8754d2b5da295ee62abed465","datavalue":{"value":"Ne\u010diporuk's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121017$BBF8EC49-6EED-45EA-B10E-7BC1FF932408","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":"Q1121017$D707C711-D3DE-4D67-8A33-8A8B258301AB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"04dfa3d7df7a5fbfe8f95ca7690d06ba0ad4a6ea","datavalue":{"value":"https://doi.org/10.1016/0304-3975(89)90054-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1121017$48F573A9-F175-4859-942C-A49B5087B9FC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ae520ae10ff0a285d99f6ad63a78751e6656d0ba","datavalue":{"value":"W2074199536","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121017$D7992782-088E-4321-BD19-619CBB5CA0AF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121017$74429EF8-76A5-448C-9282-9D166BAC8455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"514b291bcc18717499c847de12de372fe9e5cca0","datavalue":{"value":{"entity-type":"item","numeric-id":5545524,"id":"Q5545524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121017$95BFA0F5-EC68-4B6B-BF93-0E1E6F0F81B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e266c332c8c722703a0d32ad33eb1d65fa4f734","datavalue":{"value":{"entity-type":"item","numeric-id":4131019,"id":"Q4131019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121017$6753A581-93AA-40FF-9F08-E9B1BB4FE208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8624ac8b08c43bff2290ca70392ccbd3bba72141","datavalue":{"value":{"entity-type":"item","numeric-id":3762226,"id":"Q3762226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121017$9F49007E-12A6-49B2-9313-E520CA9FF081","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9614f23922739def7c7e4dfe9bc3cebfa2c290e","datavalue":{"value":{"entity-type":"item","numeric-id":4973868,"id":"Q4973868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"880d93ca523607fff5524f3a98fae745a790e267","datavalue":{"value":{"amount":"+0.824304461479187","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":"Q1121017$91ECC4FF-C7CD-4FB6-99EF-FDC64DEC68E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"631d532687e859f2d3becae1d6f01bdb59f2b87d","datavalue":{"value":{"entity-type":"item","numeric-id":5493360,"id":"Q5493360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"370ea64fa0d9e2ef6860eac66dbc83b01ec44cd2","datavalue":{"value":{"amount":"+0.8213991522789001","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":"Q1121017$C567BFAB-2A0D-4DF4-8EA7-5DD9888262C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"790a13e529330f03f7a7f9443b8f8b2740756d59","datavalue":{"value":{"entity-type":"item","numeric-id":3690219,"id":"Q3690219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29151b5770a2b91a45888172df01510238143b48","datavalue":{"value":{"amount":"+0.8200048208236694","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":"Q1121017$57A8881C-74A5-4922-9CBB-8925A8AE6421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d34bffca204837b687155ec32630ddb690ca5a5","datavalue":{"value":{"entity-type":"item","numeric-id":3002761,"id":"Q3002761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35684b06bd5d303edf496b2b8a2492ece626ce74","datavalue":{"value":{"amount":"+0.7900671362876892","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":"Q1121017$CBE4BA6C-605B-4D98-A355-F793C4F8968D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"985b1b1cabac17114dd5628e8bbe5467101a10da","datavalue":{"value":{"entity-type":"item","numeric-id":1392030,"id":"Q1392030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56d9d15492cff109fe2ca70a35f109633c5a26df","datavalue":{"value":{"amount":"+0.7879158854484558","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":"Q1121017$532D6682-420B-43D5-8F36-FF1577D73D90","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On Ne\u010diporuk's theorem for branching programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_Ne%C4%8Diporuk%27s_theorem_for_branching_programs"}}}}}