{"entities":{"Q1613515":{"pageid":1624255,"ns":120,"title":"Item:Q1613515","lastrevid":72343410,"modified":"2026-04-14T04:15:57Z","type":"item","id":"Q1613515","labels":{"en":{"language":"en","value":"Rivest-Vuillemin conjecture is true for monotone Boolean functions with twelve variables"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1792439"}},"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":"Q1613515$0CE0C2C9-0881-4CE6-971D-756D2A60B116","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a51eb80911819568ae41c667a71593d36e294995","datavalue":{"value":{"text":"Rivest-Vuillemin conjecture is true for monotone Boolean functions with twelve variables","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1613515$DC7A6362-673F-4F0B-8B84-012A8C77A416","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"03eebd71bd003e66bd1fdb0ed4691c10bd4eddc3","datavalue":{"value":"1005.68107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613515$E7CB9454-FF04-4731-A87E-F9B7510D7325","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c1ff9ff173d00c940a0a75447c628434c5696024","datavalue":{"value":"10.1016/S0012-365X(01)00446-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613515$3241C1AA-87A2-4CF5-97A4-F42E4F0416A7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2d176dcf8014bfec2c4899579ee7ce9e18294338","datavalue":{"value":{"entity-type":"item","numeric-id":166203,"id":"Q166203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613515$A1B34889-0D07-4D0B-9B63-CB6C7413A1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"43894e976784ba64f570a2d21e3a781db6ba50e6","datavalue":{"value":{"entity-type":"item","numeric-id":1613514,"id":"Q1613514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613515$393429C7-8CAD-4D32-A789-4C50288A74ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4fc59f4567eafab16fdaccf0df8e89e49963298","datavalue":{"value":{"entity-type":"item","numeric-id":1578506,"id":"Q1578506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613515$F07C14B9-933D-418C-B3DF-0AACEFCCEBB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c7dd1fe651a8e7d69e92da7829111cb9c11ac0c9","datavalue":{"value":{"entity-type":"item","numeric-id":224542,"id":"Q224542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613515$BA3896D4-67A4-4DF7-A6F6-BCCA50E8452B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613515$3A9B4EDA-913F-412D-86F2-876E5F15A74E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04ef60e6a08d63a03521c7b80b58e0a998b63b55","datavalue":{"value":{"time":"+2002-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1613515$B69B144E-DDF2-4D19-A70B-8A6FE5FD9A2D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"45d2179db4afbb09f5783c0648d13367866f79fc","datavalue":{"value":"A decision tree of a Boolean function \\(f\\) is a rooted binary tree, whose nonleaf vertices are labeled by its variables, and leaves are labeled by \\(0\\) and \\(1\\). Edges are labeled such that edges from a nonleaf vertex to its successors are labeled by \\(0\\) and \\(1\\), respectively, and every variable appears at most once in an path from the root to a leaf. Given an assignment to variables of a Boolean function \\(f(x_1, x_2,\\dots, x_n)\\), the function \\(f\\) can be computed by its decision tree.   A Boolean function \\(f(x_1, x_2,\\dots, x_n)\\) is called elusive if every decision tree computing \\(f\\) must examine \\(n\\) variables in the worst case. It ist a long-standing conjecture that every nontrivial monotone weakly symmetric Boolean function is elusive.   In this paper, every Boolean function with twelve variables is proved to be elusive.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613515$E9CAD0CF-64A6-4479-8704-BBDBCA25066B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e82f32c91e1eb0067a512f27a8cb077a4f29f958","datavalue":{"value":{"entity-type":"item","numeric-id":640843,"id":"Q640843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613515$A1D157E8-3C79-4743-B582-4695A6CA4CCB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613515$2B5E948E-CB03-4682-90EC-F0536ECBCCCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613515$B43819DC-DD73-42D4-92C7-6138CE048AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613515$A69BEB3E-5EF1-4BB1-A556-1D626C014416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613515$08336593-0E5B-4E88-B9C6-35422DCDE400","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"52f48156c9c961b51974d99da6a148fcf9e00184","datavalue":{"value":"1792439","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613515$8E253A6F-4BEC-4936-8385-3D2A17968592","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613515$796D0C89-8D5F-4CE9-95BA-2807CB2DA3C6","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f34fc2864311445eec2005d4ddc3c401b610a03a","datavalue":{"value":"Q122927347","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613515$7E9C5937-C828-45C4-97AD-36A4C70EDAFF","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":"Q1613515$8B64572C-6815-4CFF-B9CB-FFD1CC134730","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ede68e7b2f288cc3001e743a82065051dd75e86","datavalue":{"value":{"entity-type":"item","numeric-id":1578507,"id":"Q1578507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f125945ffb5ed246d79e7e3a71e1358a341b406b","datavalue":{"value":{"amount":"+0.9461223","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613515$50F95A70-9AA6-47B3-8E7F-E4CB44E4B2EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea4b9df3e284f67bc4d231d73359b5f9961dcba0","datavalue":{"value":{"entity-type":"item","numeric-id":3335687,"id":"Q3335687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a776ebcc388b5f4a6b293d749d72c5c66399c58b","datavalue":{"value":{"amount":"+0.8321224","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613515$24620426-D607-4ADA-BBFF-D3E443226BAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"256c548d81292e24054bdb040311aea36660531a","datavalue":{"value":{"entity-type":"item","numeric-id":1960414,"id":"Q1960414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"012c2a1abd62e99773d2ca2111618bb2271b42ee","datavalue":{"value":{"amount":"+0.8245433","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613515$7F091680-8E96-42F0-A986-6D9EBD7F3DFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"148b486f82ccbe771f397cd2b0b779b0b8a1e226","datavalue":{"value":{"entity-type":"item","numeric-id":3335686,"id":"Q3335686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"103c45103d508f9e83b2d60398588212b71a9ee1","datavalue":{"value":{"amount":"+0.81387997","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613515$958E9E9C-C792-4D56-BD34-B9E080845061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"739c39aeefec7713bacb2fa86ac5693793f2b61d","datavalue":{"value":{"entity-type":"item","numeric-id":1847362,"id":"Q1847362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"086cbdc89bfdc764cdf9edb5074ba279ce874b9c","datavalue":{"value":{"amount":"+0.8119569","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613515$E675CD5C-0949-49C6-B458-3F8B9C25246A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48ab603e5d829ceee1b50ecacac96cc655928e5b","datavalue":{"value":{"entity-type":"item","numeric-id":5043579,"id":"Q5043579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"643253869ce406eefbd997e910c14f337c82c178","datavalue":{"value":{"amount":"+0.8075806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613515$9335DB5A-DA75-4189-B905-68369C199385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"023b6af3d56088941e54cb900705fa78f8ef9925","datavalue":{"value":{"entity-type":"item","numeric-id":1667447,"id":"Q1667447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21545b140e1d900af2b8c677fb3f180851bd3b2e","datavalue":{"value":{"amount":"+0.8056007","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613515$950C3FED-A431-4032-9BA5-C2A81C2597B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc7f5f680c589ecac91d4a5ee87a789fb4d40816","datavalue":{"value":{"entity-type":"item","numeric-id":5491236,"id":"Q5491236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fe0abcb1e98505f547a51163c0ae2bd4e3c8f6f","datavalue":{"value":{"amount":"+0.80343634","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613515$57F5E11B-98FE-452F-B9F4-D33A84C66ADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f7c3cb1c2df4a084edd1d05869dcf87c18b8564","datavalue":{"value":{"entity-type":"item","numeric-id":3597523,"id":"Q3597523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56e3c7513b857b6980623c9f674795bf8798567d","datavalue":{"value":{"amount":"+0.8007331","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613515$9F067C3A-17BF-4BED-B9F3-B9CDA66F36E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc3c2b8b515ab766405419866b5d7936fd003b86","datavalue":{"value":{"entity-type":"item","numeric-id":1850027,"id":"Q1850027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d7ed009b120afeba3565bca2e03c30cfeb80d1f","datavalue":{"value":{"amount":"+0.79828686","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613515$F34E7862-F7A6-4912-A706-9AFF10C2F3F2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Rivest-Vuillemin conjecture is true for monotone Boolean functions with twelve variables","badges":[]}}}}}