{"entities":{"Q1275996":{"pageid":1286746,"ns":120,"title":"Item:Q1275996","lastrevid":46605999,"modified":"2025-12-25T04:52:01Z","type":"item","id":"Q1275996","labels":{"en":{"language":"en","value":"General upper bound of circuit complexity in an arbitrary infinite complete base"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1240164"}},"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":"Q1275996$6A737468-A408-4C75-9A0D-63DA2951C085","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"165629a73f7c629dab79af408a663c2f71242c7e","datavalue":{"value":{"text":"General upper bound of circuit complexity in an arbitrary infinite complete base","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1275996$B55CFF9B-E7C6-470B-BC78-9B4884C9DC40","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aa70d85ba124c1dc02c7f5e93c1ecfb3c3a0f41b","datavalue":{"value":"0909.94023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1275996$4E88AE02-DF6A-4A55-A91F-8E37F0350C90","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a6c4f0aec78155516b50f3c1a92718473c1db63","datavalue":{"value":{"entity-type":"item","numeric-id":226474,"id":"Q226474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1275996$D0A6B27A-8353-4C6C-B9D8-2CA52835E181","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6c13805eb53dbd00bf0343bc22d19b4be9e16872","datavalue":{"value":{"entity-type":"item","numeric-id":187667,"id":"Q187667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1275996$77D56D67-A5D4-4D4E-9A87-A3B65F4484EE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e6d31144137b87943f8d6bd69e48d5d402876b49","datavalue":{"value":{"time":"+1999-01-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":"Q1275996$4C73A065-E625-44E1-8C09-5132D224284A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e39d7e5619ca51c6bee67687598fee74815d1607","datavalue":{"value":"Let \\(A\\) be an arbitrary functionally complete system of Boolean functions where each function depends essentially on all its arguments. The complexity function \\(L_A(n)\\) is introduced by the formula \\(L_A(n) = \\max_{f}\\min_{S} L(S)\\), where \\(L(S)\\) is the complexity of the circuit \\(S\\) and \\(f\\) runs over the Boolean functions of \\(n\\) variables. The note deals with the proof of the following assertion. For an arbitrary infinite basis \\(A\\) the relation \\(L_A(n)\\leq C\\cdot 2^{n/2}\\) is satisfied for all \\(n\\geq 1\\), where \\(C\\) is an absolute constant (i.e. independent of the basis \\(A\\)).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1275996$58773FAF-DBB5-44BD-A510-10F8E9704E80","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1275996$2391CDAB-D101-4F05-9C81-D366A388FD93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1275996$11F33C7B-E655-4DBB-B9CC-DEF30B752D36","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ad31bbb040168172d5d37002dbc85645be9f0648","datavalue":{"value":"1240164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1275996$FB9372BC-5963-491E-BC86-5DB3AD8DD64E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e09ab337a61ca345df5d5ce1296d3077409da21","datavalue":{"value":"complexity function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1275996$A3009C1D-AF54-4AA2-841A-A94549547317","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd8290f62a963c56d6f80f9b5cf83f4e6c13d8b0","datavalue":{"value":"general upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1275996$BC329A93-352C-48BA-B608-DC57271123DD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c8642b90facb009fac3e5d2aeec487d0b254cbd1","datavalue":{"value":{"entity-type":"item","numeric-id":593066,"id":"Q593066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1275996$025344A1-2A31-4EC6-9443-AF99927A7B9C","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":"Q1275996$FB928201-F9B0-4DEB-B954-D93A5D57E23D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4492b6507b72026889a359f6715503f50d1e7d5","datavalue":{"value":{"entity-type":"item","numeric-id":4830984,"id":"Q4830984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27f8ad170256c2bcd2025108fc434073f04a94d6","datavalue":{"value":{"amount":"+0.870632529258728","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":"Q1275996$3947BAD7-62AC-4B17-AD15-6185BD287A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db4b2f873e9fb745bc0343fa2418e6fb2fc53885","datavalue":{"value":{"entity-type":"item","numeric-id":3364511,"id":"Q3364511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"992308ceee34a05bae471e1f17d813b6115d79e5","datavalue":{"value":{"amount":"+0.8385352492332458","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":"Q1275996$154BB427-A8C9-48C1-B026-C37359F9BDAE","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":"bcc579a7e10ea16bbf49753648e139d13eaa31ca","datavalue":{"value":{"amount":"+0.8319254517555237","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":"Q1275996$D1382991-9DD7-4E40-A1A4-F77CE2CE95AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5e5ca6c12e42e28c4c323ed4d9b7f40799393a2","datavalue":{"value":{"entity-type":"item","numeric-id":2295973,"id":"Q2295973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ac574a5b4406539a7c2797169122120b28be778","datavalue":{"value":{"amount":"+0.8202316164970398","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":"Q1275996$57DFCE34-425F-4C4F-890B-05F3DDBEE3D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"144bfd23115a9d8d94d8c0d537eafcdd0f68b7b6","datavalue":{"value":{"entity-type":"item","numeric-id":1594916,"id":"Q1594916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a52a3283558538487bc87c079a3bd2071f2e32e","datavalue":{"value":{"amount":"+0.8192976117134094","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":"Q1275996$4FB7882D-5618-455F-BD55-E9E438D34F1A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1275996","badges":[]}}}}}