{"entities":{"Q5936693":{"pageid":8113495,"ns":120,"title":"Item:Q5936693","lastrevid":97640540,"modified":"2026-06-05T15:09:11Z","type":"item","id":"Q5936693","labels":{"en":{"language":"en","value":"On the mean evaluation of polynomially reducible Boolean functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1614374"}},"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":"Q5936693$AE3A45AA-B6A6-4DEE-8AAB-D146D3F1B109","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6caa94bbb60e39111d985fb79045b040437e961d","datavalue":{"value":{"text":"On the mean evaluation of polynomially reducible Boolean functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5936693$E41DA910-D115-48F8-ABD4-3EB0B3B70013","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6d308a3c7ee9056666b5020a3789be40e9343fae","datavalue":{"value":"0964.94032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936693$C04E32F4-2144-469B-AB24-1FC466A78AE6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1542a73ffc22f2d225abd6fdd963c595b4d028f1","datavalue":{"value":{"entity-type":"item","numeric-id":187705,"id":"Q187705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936693$D3AFE1C0-7470-456D-A7E5-6581570BB44C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6c13805eb53dbd00bf0343bc22d19b4be9e16872","datavalue":{"value":{"entity-type":"item","numeric-id":187667,"id":"Q187667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936693$51AA04E2-5D25-4F5C-AD06-E986EFBC2F5A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"645eb1073c4ef66310005fd852d0af24336cf4ca","datavalue":{"value":{"time":"+2001-07-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5936693$8919F1C6-80E1-4048-94D1-3EF6EAB12572","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ff5d4ef0a21bbff438b2b04426dcdcd95cb6cd3","datavalue":{"value":"Let \\(P(x)\\) be the value of the program \\(P\\) on the set \\(x\\); \\( T_P(x)\\) is the working time of the program \\(P\\) on the set \\(x\\); \\( T(P) = 2^{-n}\\sum T_P(x) \\) is the average working time of the program; \\(T(f) = \\min T(P) \\) is the average time of computing the function \\(f\\). Let \\(g\\) and \\(f\\) be Boolean functions of \\(n\\) variables, \\(g\\) be polynomially reducible to \\(f\\) and  \\[  \\lambda(n) = \\max \\frac{T(g)}{T(f)}.  \\]  In the paper it is proved that  \\[  \\lambda(n) = \\Theta((2^n/n)^{1/2}). \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936693$B4A65502-D789-4437-AB9C-794E15CD8772","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936693$1793B146-0EC3-4A48-8F7E-72D1052DEEA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936693$229CF995-1838-41C9-9874-6849C33FE132","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0569d872ebbda698c5f2d709ac574c8b1bf2df35","datavalue":{"value":"1614374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936693$A96C88A3-2E17-4FCA-B5A5-BB97F9A26B7C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936693$EB036ED3-C171-41AF-815F-3A20B7D5FC5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f3f87d304d03ea570f6d652bf2ffe6619884ad4","datavalue":{"value":"average time of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936693$31286429-AE95-47B0-8AEA-D1F3028672C1","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":"Q5936693$49EEE44A-4E98-48A8-B6A7-AEE453390AE3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ced587bbf3a99edcffe6639749b3c572ed23fd88","datavalue":{"value":{"entity-type":"item","numeric-id":5958111,"id":"Q5958111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"470fa26ce1020019175cdd972cd628373ed3b2b2","datavalue":{"value":{"amount":"+0.9001924","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936693$509857F8-6E92-4082-A9DB-C9B006C713B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3650ff982f7b09cc304c67da1f9aa2f464e955c5","datavalue":{"value":{"entity-type":"item","numeric-id":1943917,"id":"Q1943917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2a25ebde03b80e62ebacf16bcba1f9fcad1a482","datavalue":{"value":{"amount":"+0.8867028","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936693$7B6E4FC8-8A56-44C3-AE9B-25817A1EB28D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10244f636439c2f69380574916d6a5b62c000f4a","datavalue":{"value":{"entity-type":"item","numeric-id":3335526,"id":"Q3335526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5849e5d826d199301066d09327a22c9ad1c5105","datavalue":{"value":{"amount":"+0.8841592","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936693$5AF5EFCF-56B1-4E7F-B800-694390358F73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e7dccdac77ea37bac741d8b1ab9cd42db0522ab","datavalue":{"value":{"entity-type":"item","numeric-id":5951317,"id":"Q5951317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5da5acefaf55c294359f3d3d0d139a2bd59aa35a","datavalue":{"value":{"amount":"+0.8790007","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936693$EAE91B67-BEBC-43D8-9DE1-9C09D1052D38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa2a7b89cfd5dfc7223bbdec7f8deb35281db00f","datavalue":{"value":{"entity-type":"item","numeric-id":2354498,"id":"Q2354498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7f87ff758c40977ea4c35815ea72855fbfe8ba5","datavalue":{"value":{"amount":"+0.8782025","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936693$1573D3E0-C6CF-482E-9D32-9C5BB2388036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e26604ac28efddc378e666c5bbee9e8b44e0ddbe","datavalue":{"value":{"entity-type":"item","numeric-id":4875435,"id":"Q4875435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfee7e61cb7a6a3d00c5ecc41fdbc846b43b6812","datavalue":{"value":{"amount":"+0.87784386","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936693$8FD9A97B-3DD8-46F0-8BD2-BAFB77C36769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5653d9b8c43acd820da6f5b027288450ea80ba5","datavalue":{"value":{"entity-type":"item","numeric-id":3202956,"id":"Q3202956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d6ae69685e44c36aef962ea84167867e7824e26","datavalue":{"value":{"amount":"+0.8772621","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936693$85DF6517-4DA2-4B6F-BC0B-81886F2A3C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8be6aa2ab25f8a3351e030b9826f41dbb58c8492","datavalue":{"value":{"entity-type":"item","numeric-id":1918784,"id":"Q1918784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"380ffdaceec15aec51f44508ecb75f82328afbf9","datavalue":{"value":{"amount":"+0.877218","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936693$7FCC73F7-7EDE-48D1-9427-6798873FD8BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e97b2869af05f7812070fdecce3594813d681461","datavalue":{"value":{"entity-type":"item","numeric-id":4836159,"id":"Q4836159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2acfad176aed3298acf2e1163158f00c3e0ef1de","datavalue":{"value":{"amount":"+0.8770181","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936693$28FC9632-E7FF-4EB1-866C-09100B5E9B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5f8d988279c11007471e3095dc6655756ea195f","datavalue":{"value":{"entity-type":"item","numeric-id":4976406,"id":"Q4976406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a25a35f9a8ecb8a155effa22a5fd2a9bdf5c1b0","datavalue":{"value":{"amount":"+0.8756775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936693$3C2369AD-DD83-4924-9166-31A4E16E3382","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the mean evaluation of polynomially reducible Boolean functions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_mean_evaluation_of_polynomially_reducible_Boolean_functions"}}}}}