{"entities":{"Q1183575":{"pageid":1194324,"ns":120,"title":"Item:Q1183575","lastrevid":70204833,"modified":"2026-04-13T13:09:09Z","type":"item","id":"Q1183575","labels":{"en":{"language":"en","value":"The complexity of the parity function in unbounded fan-in, unbounded depth circuits"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33394"}},"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":"Q1183575$1947DB3B-B513-4B9E-B435-9E24203E65D0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c5fd1ede9afb0b0767c13d3d1ff0788b52b258d5","datavalue":{"value":{"text":"The complexity of the parity function in unbounded fan-in, unbounded depth circuits","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183575$3322810B-FBA9-4402-BDB5-83A7FA0F5EA2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"efb492fff90b1a9b818b81490082651d481289ce","datavalue":{"value":"0749.94025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183575$DECF3476-CB40-401C-B10C-10EAB782C58F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1b30f4a5ba2259299d704a8bab26b58d6dd3f014","datavalue":{"value":"10.1016/0304-3975(91)90052-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183575$A41ED0EC-5E93-49A4-A90B-04F220164C62","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"00b3e57da97cbc00a7ce7385e258f05ae9a6ec6b","datavalue":{"value":{"entity-type":"item","numeric-id":171935,"id":"Q171935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183575$903F630A-4B76-4309-858E-33CDB176A5A2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183575$72CC4BE5-0937-4A26-BC05-AF1F7FFB64B7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183575$7012B23A-7A21-476E-9E14-41EED151E8F8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b4b6e4f3b9660c702efe1239cf4fe23c78e827f5","datavalue":{"value":"An involved study of the complexity of the parity function \\(f_ n\\) of \\(n\\) variables realised by unbounded fan-in Boolean circuits is presented. The number of gates of a circuit is considered as the main complexity measure, but the number of wires is also investigated in some cases. Several optimal and almost optimal (lower and upper) bounds on the complexity of \\(f_ n\\) for distinct bases are established. The proof techniques used include several nice ideas, and are interesting for everybody working in Boolean function complexity theory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183575$F8EC8F21-E210-49BF-BD98-3DD3EAE03B45","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183575$1A5BE6CC-7518-4E2F-88DF-FB24A266E93A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183575$A0DCCE1A-CD05-437F-A77D-3B8D969F7473","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"10ffcf0fcd70eb421600dd7a9881e350278c8289","datavalue":{"value":"33394","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183575$66E2286F-EB55-4CD7-A4C3-4904E042825C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b31bd7b1651dc597108fc8744cb692090d1cc9f6","datavalue":{"value":"complexity of the parity function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183575$B7374861-091F-4233-B5D8-8F23F7213B27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35e2484e5d1f7961618fcd8f7fcf8d931f1ed344","datavalue":{"value":"unbounded fan-in Boolean circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183575$3C65C40D-30B8-4F34-A4A3-0CDD71E11637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ec171027d1650ccf5b7f14821b846bd5dc75680","datavalue":{"value":"complexity measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183575$5C525107-7BC8-4987-A185-20E453F8CE8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fad4ae0b50deb9b3d8c6330f74bcbe05b4359a4c","datavalue":{"value":"Boolean function complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183575$0FE594CD-AF1D-40BB-AECC-116F6A5E8DA5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"633fdcabf2e644e3cc3929da0924cb1d112f41ed","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183575$BD7C448F-66E2-438B-B5B0-C831E95FEE9C","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":"Q1183575$F1077A41-ED11-4C8D-82B8-6F688C01A7AF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3362882171a900c17a3f0d637d2cfd782274d3d4","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90052-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1183575$FCDF97D9-6DCF-462B-BF21-678D744409D5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e212a09698dd2933586cf5e478873d362203f87e","datavalue":{"value":"W1967516941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183575$1119F3BF-0AD8-4F63-89C3-908ADEE0C704","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3aa57810f0528ce2438cd0f484c242c53bb4e54","datavalue":{"value":{"entity-type":"item","numeric-id":3325043,"id":"Q3325043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183575$54890158-5891-46F4-9DC4-80C50B77C315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74679314f3a4bdcbae7b5898cd68f64667d27e59","datavalue":{"value":{"entity-type":"item","numeric-id":3745772,"id":"Q3745772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183575$0C9F7DA3-F040-4F31-AB24-95FAC6633DD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"997192e4b8fa1855113844764b40071200759a95","datavalue":{"value":{"entity-type":"item","numeric-id":3751010,"id":"Q3751010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183575$9BF8045D-3793-402E-B922-0DE4C85BAD4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e76e57b1a3ef3b234943cd47766184bcb56ab049","datavalue":{"value":{"entity-type":"item","numeric-id":3586261,"id":"Q3586261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183575$F2CD1005-D82C-40C2-8C39-8893D6B298AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6036bf43f265b8908f5fed788c1a5dda8ab233cc","datavalue":{"value":{"entity-type":"item","numeric-id":1220384,"id":"Q1220384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183575$521975D2-0A2E-4AA4-B5AB-4BAB8FC24314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"165b6c4c396d8c236da6a3694e5493ec07d4bc2e","datavalue":{"value":{"entity-type":"item","numeric-id":3782781,"id":"Q3782781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183575$BDA6A3AF-4B36-4C3D-A519-4B9A4DA4B072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8624ac8b08c43bff2290ca70392ccbd3bba72141","datavalue":{"value":{"entity-type":"item","numeric-id":3762226,"id":"Q3762226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183575$51073A66-984B-4E84-915D-A38AE50A13F7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a2edeec2db68917d0328a7a8a9efbf32c73917c","datavalue":{"value":{"entity-type":"item","numeric-id":2131416,"id":"Q2131416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13e1f2feb9a0e2c606d4d095e0e0234fef250abd","datavalue":{"value":{"amount":"+0.8697215914726257","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":"Q1183575$1DC80C0D-2912-415B-BBCA-4C3D7D2CED41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b1d85d54173976c80d497f1969b7d69a946d792","datavalue":{"value":{"entity-type":"item","numeric-id":1791765,"id":"Q1791765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3111187e38b018c6e4ddf4f81c2b28a83f6b4504","datavalue":{"value":{"amount":"+0.8496333360671997","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":"Q1183575$963D02C5-7E23-456B-A3F9-A92E32EF139B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fab7e75b2a9776cd1828fbce1cd7d8858bed1b72","datavalue":{"value":{"entity-type":"item","numeric-id":2332856,"id":"Q2332856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e675e15b68f62b967baefeaa14b5d15b76baa45","datavalue":{"value":{"amount":"+0.8208471536636353","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":"Q1183575$A5EB75CC-F104-4EEC-B9AF-747B8019B296","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc4845dba694434ce7e60c4d9a6ae9d5ae4f7f43","datavalue":{"value":{"entity-type":"item","numeric-id":1350754,"id":"Q1350754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1c9da0f6d92667ef95d3692e8b373f0555d13c2","datavalue":{"value":{"amount":"+0.8193348050117493","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":"Q1183575$549657AD-5652-47D4-ADA4-D81E8963666E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b6faa9d45f6c3ab149026b87593d2638f626668","datavalue":{"value":{"entity-type":"item","numeric-id":255774,"id":"Q255774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a19de7c667714a277bb7176a06d04d0271ffcc1","datavalue":{"value":{"amount":"+0.8171103000640869","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":"Q1183575$73C77908-1E00-498E-B179-B78A4C87EC7A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of the parity function in unbounded fan-in, unbounded depth circuits","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_the_parity_function_in_unbounded_fan-in,_unbounded_depth_circuits"}}}}}