{"entities":{"Q2892023":{"pageid":2902748,"ns":120,"title":"Item:Q2892023","lastrevid":84882218,"modified":"2026-06-03T04:21:31Z","type":"item","id":"Q2892023","labels":{"en":{"language":"en","value":"Computational complexity of Boolean functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6047155"}},"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":"Q2892023$AD29445E-2CDD-4960-B826-AAA0918B5D49","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5175ed3312bb35b1008fadd5ca5e1dfcc453c324","datavalue":{"value":{"text":"Computational complexity of Boolean functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2892023$F4043AA5-3898-43EE-951F-DEB750049C5E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b2c61bddaf813e7cb423d2f5231afdb6d0bdf1b4","datavalue":{"value":"1257.94041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2892023$54D31D18-43D4-4050-A3E9-4C1831A55CC3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f860f69f39e97a44d9dc91185aaf877a84e0b855","datavalue":{"value":{"entity-type":"item","numeric-id":2710703,"id":"Q2710703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2892023$1A5A8B93-E87C-491F-A92C-A807D341EF0B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"40ab5745469d78369b52e28b19a08e5e326e72ca","datavalue":{"value":{"time":"+2012-06-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2892023$53366F09-A30B-4D5A-9961-A908E26A33C2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a252ac0e16e7cd1b816dd4d8c55ab05955b53869","datavalue":{"value":"94C11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2892023$4A99BD37-23D9-4945-9B81-D9F7DCC4F375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2bf534479b9242e973ca011ffc03f5c515318eab","datavalue":{"value":"94D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2892023$8DACE7D4-47C5-46E8-87E9-AB68A7965A34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0c11e1636e28bd1a59d5342c1523bca4bf56a601","datavalue":{"value":"68Q06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2892023$A3E6DB0E-DF89-4EA9-AFA9-76642E1ECD15","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ab9bbd5c1a85ceb93484b360f660501e0871dc3f","datavalue":{"value":"6047155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2892023$8CF21116-DACA-46FE-AA58-41B65569CA32","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"137d6794a6efe35571397acc6ff9f6acadf30893","datavalue":{"value":"survey paper","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$57F4FBEF-004B-4833-9077-B616E9C676D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe708dcce91d571d1ebd3853007f0b16521f4c8a","datavalue":{"value":"Boolean circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$673FB404-B2F6-4D89-A6D1-2432AF9584DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$4799545C-8856-417B-9B96-6E131A910550","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b17f05e4289c7582cd773cdd4edb907a56b3cc","datavalue":{"value":"disjunctive normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$7BE7C556-971D-4F72-BBD0-E3D4E9B30998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ffd82e58eb31a80abcafc224636104da55e7f6e","datavalue":{"value":"cellular circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$391CB91B-88D4-446A-9D6F-6BB36D0247B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d8f0f873c8688bfad50f7fb3f0da4dca4986acd","datavalue":{"value":"contact network","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$C622BA64-18F7-44FB-92AA-3FDBE92889B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1b275c07c5d90e8b3b9b9b4b4a981d3413144a4","datavalue":{"value":"logical formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$14AAE69D-4D28-41F8-949F-D48E051E3B79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$E79461AF-0ED9-4683-9A11-DD9CFB50F475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ecf518b981614c83128f6bb6bfdea5422694a10","datavalue":{"value":"complexity of circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$7896077F-30AF-488A-8EE5-5825CA163DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfc88ef9f420d6a65bcffd37ca98aacd56d8d895","datavalue":{"value":"series-parallel contact network","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$81B17C3F-FEFB-4F36-93ED-89A3932D7784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5df7f35073d2d93de90ca628d7e3c4d5874bd9c","datavalue":{"value":"partial Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$55040F5B-321A-407A-95EF-31C025CBF6CD","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":"Q2892023$AFE26196-EDF1-42E6-8E51-F5A1B193BE85","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"50c18b0d83aeeda4ddb704a57e6e4aa8c90392ca","datavalue":{"value":"https://doi.org/10.1070/rm2012v067n01abeh004777","type":"string"},"datatype":"url"},"type":"statement","id":"Q2892023$1AB11062-7707-4C7F-972F-26AAF5DE710F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c52fb4ca038808d64f97fbeab545a5d1da1a472e","datavalue":{"value":"W1993668330","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2892023$B00A6B6A-5A48-4B90-9E5E-B176568D864E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"97bcd1b8de67ff0d088b6af62ce28302eacaf3f5","datavalue":{"value":"10.1070/RM2012V067N01ABEH004777","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2892023$5573A332-D8A6-4AAC-B6F6-496B37CAAEE4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"960c31af6da1e7b1e56c1337d5f3e4367fbab3fc","datavalue":{"value":{"entity-type":"item","numeric-id":6539509,"id":"Q6539509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2892023$66BA4327-0494-43A4-9B54-8EABF204470E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8f1e6183221ca2026acb2e8ecf05b30ceeb3a6b4","datavalue":{"value":"This survey is devoted to a brief presentation, without complete proofs, of the main results over the last sixty years related to the complexity of computation (realization) of Boolean functions by contact networks, Boolean circuits, and Boolean circuits without branching. It contains three parts: Contact networks (arbitrary contact networks, series-parallel networks, planar networks, locally non-planar networks, cellular networks, networks without zero chains, networks of bounded degree, Khrapchenko's method for \\(\\pi\\)-networks, symmetric Boolean functions, invariant classes of Boolean functions, lower bounds for the complexity of minimal contact networks, disjunctive normal forms), Boolean circuits (arbitrary Boolean circuits, circuits with bounded branching, threshold circuits, circuits with delays, cellular circuits, circuits over infinite bases, circuits over bases containing elements with zero weights, Lupanov's principle of local coding, partial Boolean functions, depth and delays of Boolean circuits, implicit and parametric expressibility of Boolean functions, polynomial lower bounds and high lower bounds for the complexity of Boolean circuits, methods of Razborov and Andreev), Boolean circuits without branching (complexity, circuits over bases containing elements with zero weights, depth and complexity, lower bounds for the complexity of Boolean circuits that compute particular Boolean functions).NEWLINENEWLINE The reference list contains 165 titles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2892023$9DFCF671-0026-4BD1-82C1-B981342B3133","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2892023$86FD8C29-A57C-467D-864E-BB8B64CDF7B1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d0520280c8d43d7a113cb9c392391e5bef5fd0f","datavalue":{"value":{"entity-type":"item","numeric-id":3762226,"id":"Q3762226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf1e5a4fc0a97df65574c05f226a2ce5a69b16ba","datavalue":{"value":{"amount":"+0.8696797490119934","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":"Q2892023$FF523C1B-4174-4856-81C6-0A9B53151E76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d2760ec8c53fe7e856e779967c14bee69c49ad9","datavalue":{"value":{"entity-type":"item","numeric-id":3980818,"id":"Q3980818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0fa2028fca1ec6c80a8fa06422d841b7f1a6f6b","datavalue":{"value":{"amount":"+0.856009840965271","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":"Q2892023$AF9E246B-BF4B-4A04-BB4D-25D50E3480E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f91aa5f516439bf23161b45a6b28104d81a3a7ae","datavalue":{"value":{"entity-type":"item","numeric-id":3496295,"id":"Q3496295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0fa2028fca1ec6c80a8fa06422d841b7f1a6f6b","datavalue":{"value":{"amount":"+0.856009840965271","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":"Q2892023$47610BC7-0FB4-4236-A7F4-4BF10AD46A9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f1b32388cdc3f174fc21cb28be66f3717ecc140","datavalue":{"value":{"entity-type":"item","numeric-id":3994882,"id":"Q3994882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9911ef80913496183a0a84778eb4af759e84200","datavalue":{"value":{"amount":"+0.8376046419143677","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":"Q2892023$C5425D85-8C4E-4BD5-AFCE-6751A5D5FCAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07360cc2624204e63ffd07fde82cee5e3570331f","datavalue":{"value":{"entity-type":"item","numeric-id":4692286,"id":"Q4692286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b09f775a56894da17bdceb685ef13e8711e2a18","datavalue":{"value":{"amount":"+0.8354806303977966","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":"Q2892023$71FF997F-87F7-4073-AD8E-5EA8D0D1F524","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computational complexity of Boolean functions","badges":[]}}}}}