{"entities":{"Q5954083":{"pageid":8130885,"ns":120,"title":"Item:Q5954083","lastrevid":47733814,"modified":"2026-01-02T13:43:21Z","type":"item","id":"Q5954083","labels":{"en":{"language":"en","value":"Lower bounds for the complexity of restrictions of Boolean functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1698509"}},"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":"Q5954083$F73D7AF8-EE2F-4318-81A4-9EFE9153744E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a6a434af29ebbaad3870e52c70847abd44f3b569","datavalue":{"value":{"text":"Lower bounds for the complexity of restrictions of Boolean functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5954083$23739612-9F6D-40E4-9E79-E62EF836A05A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"06bc322e0e2b8827aa8a5aa6afc68dad2f170730","datavalue":{"value":"1006.94035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5954083$2BDA5B06-1B23-48C9-B640-1986586473F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa6ad49491ff56dae0b07dcda54158994350a931","datavalue":{"value":"10.1016/S0166-218X(00)00361-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5954083$EA6828CC-0EC7-4715-953C-6A1F7F45D74E","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":"Q5954083$12F8E751-5B4D-4AAE-A3F1-38EE5BF4A89F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5954083$178CBDF2-4266-4B27-8BC6-A2A914CFFEA7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"db9614d00581dc56211cb141a09c08b427132894","datavalue":{"value":{"time":"+2003-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5954083$405759A9-4415-4AAE-867E-3BF55644FDBD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ba02aa352e99bf26e9e5022623719432663b991","datavalue":{"value":"Given a Boolean function \\(f\\) and a set \\(M\\) of domains, the circuit size complexity of the most complicated restriction of \\(f\\) to some domain in \\(M\\) is studied. Upper and lower bounds, depending on the domain size, are established for wide classes of Boolean functions. Similar results for other complexity measures (e.g., formula size) are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5954083$C643119C-1E41-4446-AE1A-CDCF619DEC7C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9cda603722202722f19339c0e84295bbe19098fb","datavalue":{"value":{"entity-type":"item","numeric-id":208765,"id":"Q208765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5954083$1FD39D0F-99F2-48D3-A461-96441B2A9723","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5954083$423EA24D-A264-4944-B7AB-DB319845734D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5954083$2F23E6A7-F546-46A6-8D07-DF1EECB999CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5954083$9DC6ED34-B31B-409D-8B28-DA6BCAB32BDA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"624cf56e2c38effa2febc411d5ff09fcb6262768","datavalue":{"value":"1698509","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5954083$AEDEB25C-EBD9-459E-BF7A-7E90E66BC3F5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q5954083$0A6C4BBF-3FEF-4A3A-9171-966AC009DF48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67c7c5c1e60fb9544c4f956e5147ace48d276f69","datavalue":{"value":"circuit size complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5954083$379D258B-DF41-4DDD-9F38-2DA237723577","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":"Q5954083$4C36D871-311C-4D05-A6A8-2C6519FB9BF9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fc510b8f4745ca24f9c6e8369687fd807133d8d","datavalue":{"value":{"entity-type":"item","numeric-id":5752496,"id":"Q5752496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5954083$F54E21BE-1281-4588-B1B6-F1DFF1F4B6D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4f7c956fd735522d219877e7588753447b90889","datavalue":{"value":{"entity-type":"item","numeric-id":1380287,"id":"Q1380287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5954083$C9CEEB75-0EC6-438C-8668-15BC842BFEBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00b22ea67e868911adffe7b374b7dc64fa471f25","datavalue":{"value":{"entity-type":"item","numeric-id":5954082,"id":"Q5954082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5954083$0AE0EE07-F31B-4D2F-A2E0-8DEEEC9AE96F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e04fb3d6e6c4a2c08e19cd7148fa430c4441e3d3","datavalue":{"value":{"entity-type":"item","numeric-id":3822102,"id":"Q3822102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5954083$B906062F-F3B5-4668-9E9F-24232A91749C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"136e727bc9ab9e9097768be974f466ff2b48d74f","datavalue":{"value":{"entity-type":"item","numeric-id":3125953,"id":"Q3125953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c800fd54262f22f56e343b057477036e804843d9","datavalue":{"value":{"amount":"+0.9032433032989502","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":"Q5954083$697F304A-C361-48D0-A334-848449BC97EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce963ade31967596c0692ea4f09f82e068865f45","datavalue":{"value":{"entity-type":"item","numeric-id":1380287,"id":"Q1380287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c4ba46202eccea3dffc39c37ec53013694bdeb8","datavalue":{"value":{"amount":"+0.8941519856452942","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":"Q5954083$35B85668-0EF2-48C9-ABF4-D5F7A238D863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64151fcec3c1d5c36d0cccfb62de57afe7bc355e","datavalue":{"value":{"entity-type":"item","numeric-id":3576211,"id":"Q3576211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11e887aff74303e8b3dea6bab14a830341303daa","datavalue":{"value":{"amount":"+0.8026822209358215","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":"Q5954083$EB173F8D-8E35-462F-AD43-0E63901A96B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9aa31a69200b26a51f10ecd16e14737a4aae2ce7","datavalue":{"value":{"entity-type":"item","numeric-id":4228451,"id":"Q4228451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34164d0f1781ed9177d04abbb7516af7682bba9c","datavalue":{"value":{"amount":"+0.8004854917526245","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":"Q5954083$1884E6EF-BB76-4917-9580-934C29E98770","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":"34164d0f1781ed9177d04abbb7516af7682bba9c","datavalue":{"value":{"amount":"+0.8004854917526245","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":"Q5954083$9F434550-2A29-4FBC-B4C2-49A829DC4E42","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5954083","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5954083"}}}}}