{"entities":{"Q790083":{"pageid":791931,"ns":120,"title":"Item:Q790083","lastrevid":42695460,"modified":"2025-07-08T13:49:48Z","type":"item","id":"Q790083","labels":{"en":{"language":"en","value":"A measure in which Boolean negation is exponentially powerful"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3847302"}},"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":"Q790083$019DC05F-C768-434A-BD01-CB78505905A1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bd302a070413d8159391d5f11d3a5c1ec7529c3c","datavalue":{"value":{"text":"A measure in which Boolean negation is exponentially powerful","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q790083$E5C12309-1366-47BB-B3FD-4A0C66034E21","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"014fda64e7a7142c63f13a466dc1796cc780da9f","datavalue":{"value":"0533.94004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790083$1553D7C8-6018-4C69-8067-924719F39122","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"714310e2a3543f720d7635c6c4e978397cfa47c1","datavalue":{"value":"10.1016/0020-0190(83)90051-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790083$34EC0C71-83CD-4FDB-A665-76AB6FDF511A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5681c82b30ed1ba85c28893bb41a74b0da78e53f","datavalue":{"value":{"entity-type":"item","numeric-id":287137,"id":"Q287137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790083$ED59E42B-8E8E-40DA-9DBE-BB6AC6A1BBD1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790083$D43323F5-6364-456E-915F-95DE26B82897","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q790083$A728E9C5-BF9D-4922-AEB9-970E58B58938","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"175e3e814789a4f5a250d15029882dd208a8f42c","datavalue":{"value":"In this paper relations between several complexity measures for families of Boolean functions, such as circuit size, formula size, and (monotone) representation size are presented. Roughly speaking, the circuit size of a Boolean function f is the smallest circuit and its formula size is the smallest Boolean function representing f. Furthermore, a family P of functions is a sequence \\(\\{P_ n\\}_{n\\in S}\\) where \\(P_ n\\) is a function of n variables and \\(S\\subseteq N\\). A family P is (monotone) universal if all (monotone) functions f are (monotone) projections of some members of P. The (monotone) representation size with respect to a (monotone) universal family P for a (monotone) function f is defined to be the smallest m such that f is a (monotone) projection of \\(P_ m\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q790083$A04D739D-2A35-48FA-8577-F395C2521A6C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790083$4343E405-094D-4432-8DDF-5250612203D8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7edbb84f43892cc69f4bd0bf02dad6eda4d3d7a1","datavalue":{"value":"3847302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790083$DB221820-8952-4C69-B41E-B2A6EF249D82","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7a39a1c143c36b9a508b6e0aad9580fb160eda5","datavalue":{"value":"combinatorial complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q790083$6CBD8791-CDB9-4738-8E7D-D4E74A1944B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q790083$548A9C15-3881-4E11-8ED0-775F01847AF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2545ea91ae77d0f1339e7eb3010156860b7c2829","datavalue":{"value":"complexity measures for families of Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q790083$A66F2A1E-8435-4ACC-A906-D963C09E30C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b187c4653e8d6f7975e2618be03cf7aed5aac51","datavalue":{"value":"circuit size","type":"string"},"datatype":"string"},"type":"statement","id":"Q790083$3936B03E-91A6-4DF0-BACD-A1D3C307A85D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf6e47b257014c8d2d90b33c610d51efc201fa59","datavalue":{"value":"formula size","type":"string"},"datatype":"string"},"type":"statement","id":"Q790083$60A86ACA-6106-4CA4-BB79-054D435E97C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d5132dc578af36550b8aa28480c01698c80a9fd","datavalue":{"value":"representation size","type":"string"},"datatype":"string"},"type":"statement","id":"Q790083$0E95AD09-7003-4FCC-AFF6-ED07D301F247","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af61ebf07455b491078594b026930b3701f75079","datavalue":{"value":"projections","type":"string"},"datatype":"string"},"type":"statement","id":"Q790083$FD133269-B3CB-45D9-B8E5-95024A2C3826","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":"Q790083$E9AF8A3D-564D-4727-B45F-8AD5612011D6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"16ca29007b27ba115065d8d4dda4b7073dff5a4f","datavalue":{"value":"https://doi.org/10.1016/0020-0190(83)90051-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q790083$C09F5A6B-7566-4CA8-8D4F-3B2134A272B0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"98000d2ec4b49757ff855724995751d5e68d3604","datavalue":{"value":"W2062322643","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790083$D6674616-2566-4B14-9078-03DC3DA27C50","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bcea5dd1838c0d984c13b6934f789fdae7a8f76","datavalue":{"value":{"entity-type":"item","numeric-id":4138140,"id":"Q4138140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790083$8B23E347-101F-4E1E-AC48-05C2B6F01C95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8e73c4b1eb952ce21189627f2e0b84dd36494db","datavalue":{"value":{"entity-type":"item","numeric-id":3771612,"id":"Q3771612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790083$30A09766-4070-46F5-AF30-1C83145B014D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1611b8c1332531567def133e9256a2298534ca92","datavalue":{"value":{"entity-type":"item","numeric-id":4556225,"id":"Q4556225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af105d24af9c8d6e1e204472d00a1b1c8ad02189","datavalue":{"value":{"amount":"+0.81469846","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":"Q790083$67031046-1D83-4D1F-BF74-3FEADB43BD6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"189e7bcf4fc087299aa1d597fe534dd35f274c50","datavalue":{"value":{"entity-type":"item","numeric-id":5348074,"id":"Q5348074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ef0b56a49cb4916767999a0342e654167e6c232","datavalue":{"value":{"amount":"+0.79869974","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":"Q790083$C9CC8974-65E3-44E0-BA76-4308F023BB1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee3c5a1719d2cda34bc7fa267dd3608d6edd61b4","datavalue":{"value":{"entity-type":"item","numeric-id":5749290,"id":"Q5749290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a900474da6ad26a815cb7d218dd23f28da27944","datavalue":{"value":{"amount":"+0.7986997","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":"Q790083$3877CBBE-D861-4026-9F9D-5A64DAB0B6D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89d47a87ec6d3e3ab62606760bcf4dc05aab7062","datavalue":{"value":{"entity-type":"item","numeric-id":1317472,"id":"Q1317472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8174f532c0c03b4818347ffc9a3d6a4cde39ccb","datavalue":{"value":{"amount":"+0.7913507","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":"Q790083$14194FE3-916C-4117-920F-FAB6ECB34A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98558ba014a418d9036e809e8a0e1a1059531734","datavalue":{"value":{"entity-type":"item","numeric-id":3791392,"id":"Q3791392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b63714d729683c81744cace201c525859856116d","datavalue":{"value":{"amount":"+0.7893796","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":"Q790083$23841796-6394-4AB5-8D3C-D0F6DF2E8FD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7065c6ece1081e2f24dad3e29350eaff7813b21f","datavalue":{"value":{"entity-type":"item","numeric-id":276554,"id":"Q276554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ee512c5300fe350090b5577ffff0c13f4f0e17f","datavalue":{"value":{"amount":"+0.7884748","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":"Q790083$2DE1B9D2-DF98-4DDE-B6BB-2F5637A65CC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2be57859719c48677291455e0dc488a4088a256d","datavalue":{"value":{"entity-type":"item","numeric-id":5150408,"id":"Q5150408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87f139d3431cd2d71a1c5e61233e3231e363d3fa","datavalue":{"value":{"amount":"+0.7883903","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":"Q790083$13CB2299-5E7C-47F5-8D02-09E31FB873CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d5201952c3f9bad0fe186a369a473b487145274","datavalue":{"value":{"entity-type":"item","numeric-id":5253474,"id":"Q5253474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afd0fe8ec9d02158746bb42f05e66f1330fdf184","datavalue":{"value":{"amount":"+0.782166","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":"Q790083$C5F07253-B738-4FC0-903D-E3124215F462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"321060a2e8f2702a56e5cbb706cbe5c9b6a1838e","datavalue":{"value":{"entity-type":"item","numeric-id":543905,"id":"Q543905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74b32aed3de3a5e5d691b57b11317c819bcd49ee","datavalue":{"value":{"amount":"+0.77594644","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":"Q790083$B556E7DF-715A-4155-AEF5-A8103C8F66F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29aad48c05264e77c68388de35d82f5e608437e9","datavalue":{"value":{"entity-type":"item","numeric-id":4514432,"id":"Q4514432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89945eb6f7e19aac7cea98739c2d137a6cfd6826","datavalue":{"value":{"amount":"+0.77590865","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":"Q790083$FF6F6B56-CF4B-4E5B-9C77-C6255FA582E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:790083","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:790083"}}}}}