{"entities":{"Q5941440":{"pageid":8118242,"ns":120,"title":"Item:Q5941440","lastrevid":41947770,"modified":"2025-05-19T10:44:50Z","type":"item","id":"Q5941440","labels":{"en":{"language":"en","value":"An exact characterization of symmetric functions in \\(qAC^{0}[2]\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1635633"}},"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":"Q5941440$ABA1D33F-3B75-408D-B95C-53C1FE9EF7B6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d42b971a33e1d69f6f9accef9aec7c580912b56","datavalue":{"value":{"text":"An exact characterization of symmetric functions in \\(qAC^{0}[2]\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5941440$609B9CF4-9F58-4B84-867F-C7BBC5CA359A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a36978901c2cbff79d174af90c89afcc8624e120","datavalue":{"value":"0972.68090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941440$3D19F067-2B5F-4AAA-B718-88DF3A291E3A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8fbe414c9aed94c9fcfe80ea2ed14df0f8580f53","datavalue":{"value":"10.1016/S0304-3975(00)00145-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941440$18C82350-7E34-4586-8527-BA0E057973C2","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":"Q5941440$B6ADFF3A-3E32-4031-B119-90531377571A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0d780905acb67c2b1b938af03e08b68df411214b","datavalue":{"value":{"time":"+2001-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5941440$7E8A7439-8442-4CBD-B862-4B50CA3C2623","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fc8557e4b3d62eff407ed7eb051f7f4bc5cf23de","datavalue":{"value":"\\(qAC^{0}[2]\\) is the class of languages computable by circuits of constant depth and quasi-polynomial \\((2^{\\log^{O(1)}n})\\) size with unbounded fan-in AND, OR, and PARITY gates. Symmetric functions are those functions that are invariant under permutations of the input variables. Thus, a symmetric function \\(f_{n}: {0,1}^{n}\\rightarrow{0,1}\\) can also be seen as a function \\(f_{n}: {0,1,\\ldots,n}\\rightarrow{0,1}\\). We give the following characterization of symmetric functions in \\(qAC^{0}[2],\\) according to how \\(f_{n}(x)\\) changes as \\(x\\) grows from \\(0\\) to \\(n.\\) A symmetric function \\(f=(f_{n})_{n\\in N}\\) is in \\(qAC^{0}[2]\\) if and only if \\(f_{n}\\) has period \\(2^{t(n)}=\\log^{O(1)}n\\) except within both ends of length \\(\\log^{O(1)}n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941440$76B9A017-2309-4FAB-BE77-DE63800D4D81","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941440$DE1024A4-4EE9-4B16-92FE-66242B2FB54D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1bf8832f0c4931cf934cc19fa8b68745b65bf895","datavalue":{"value":"1635633","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941440$58665761-EAD4-44F8-A519-522BB5236349","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941440$65137972-07D1-4BA6-A2D3-822A9F9FAC8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941440$A1384AD1-975C-4083-9490-2786C3F41F28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd78f2bc06696d6773d40095a660efe1b5eb3eaa","datavalue":{"value":"symmetric function","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941440$37A28FED-2B6C-49F6-9883-D59020CBF9C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df2e397a86b8cc356bd87c7ff0b1a23a94a39170","datavalue":{"value":"period","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941440$BD35AF44-B3F9-448E-94D1-DAFB70461844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfd033e9c12394bd0334a7ed18c851c658ea1655","datavalue":{"value":"parity function","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941440$FA4BC002-2C20-4F12-9E32-5DB112B510CC","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":"Q5941440$7E554BEB-5BF4-43BF-BB90-CDE82EBB7D2E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"957892286a77298fd7faca30f1f60dbb53f94696","datavalue":{"value":{"entity-type":"item","numeric-id":1054720,"id":"Q1054720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941440$F349201F-2001-4419-B500-06E10D082BA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf09980eb701e5a3f32afbfa623fd5896cafe9a8","datavalue":{"value":{"entity-type":"item","numeric-id":1330793,"id":"Q1330793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941440$7D1A0895-C2F6-4C1A-89BF-95F5E5B32B3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"698a1c7280e2094de881e13a5c815fdebbfa914c","datavalue":{"value":{"entity-type":"item","numeric-id":1346614,"id":"Q1346614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941440$F65EB8EA-E8F9-4ED2-8386-BC9BD7BE6C2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d23d482bb4eeb3cb784fe68510e3d484e171fb1","datavalue":{"value":{"entity-type":"item","numeric-id":1107989,"id":"Q1107989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941440$B1D6D011-C045-4A86-BE50-44CA54D71298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fbf5f7df9a33c83e0132a26abaf010e9bbbdce3","datavalue":{"value":{"entity-type":"item","numeric-id":1063574,"id":"Q1063574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941440$665A4A43-6316-437E-A1D4-A1DE37273A62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941440$F58EF847-3EB4-4990-AF8D-DD8B272F7501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ffb7c4897464eade24b984dc253233d6968fb77","datavalue":{"value":{"entity-type":"item","numeric-id":1095871,"id":"Q1095871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941440$31843A56-4C67-4C0D-AEF4-8DCC0E1E2521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cc0e8e5579990d0e88d71762eb3351840410ea7","datavalue":{"value":{"entity-type":"item","numeric-id":4281556,"id":"Q4281556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941440$39DD0962-3DC9-45FD-AEC5-D454D8429D2D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"387d7d51d839830c88a5c3dbfe8ef73fb0c8a749","datavalue":{"value":{"entity-type":"item","numeric-id":4218418,"id":"Q4218418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3a3ded58dbc67e3f030547cb99c939714b213f4","datavalue":{"value":{"amount":"+0.99955094","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941440$05DEC7D3-484C-4AD6-94EE-C8809B12B7E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5128530cdf80b889281f77ad94e296b743a1af50","datavalue":{"value":{"entity-type":"item","numeric-id":2264030,"id":"Q2264030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51822a2b0fedfd121110c966b8fa763819cf6440","datavalue":{"value":{"amount":"+0.89190733","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941440$37D94232-0591-4566-AD8F-7EB5D10F19D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41a92d0279f61f37398c27465d575ea691a77408","datavalue":{"value":{"entity-type":"item","numeric-id":5949439,"id":"Q5949439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ef656bc4ac3e95b3c2ccf93f58af7a3c40961b5","datavalue":{"value":{"amount":"+0.8805548","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941440$45596F46-AEF6-45EA-8F67-5464183FDB57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f4463001d439fc4e78ada29c802751dca737707","datavalue":{"value":{"entity-type":"item","numeric-id":2868759,"id":"Q2868759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e804fb72c156c64fbeb61f17eee966cf1c907cd5","datavalue":{"value":{"amount":"+0.8771939","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941440$6EC54CB5-EE80-4902-9568-8775F715139F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83a91563cc0227f1db95fa7eeaca6c815301d581","datavalue":{"value":{"entity-type":"item","numeric-id":5154976,"id":"Q5154976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c87292bcbe5ebde62ab426002335339c3338711","datavalue":{"value":{"amount":"+0.87344885","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941440$52CE5A86-0FE8-4153-BA2B-6DA40B32B52F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79f25e7d15defd7c9a43407f85fccfb1d30a71b9","datavalue":{"value":{"entity-type":"item","numeric-id":1584652,"id":"Q1584652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ae4ba29822c8ca9a0cdbcada4d584695164b3e2","datavalue":{"value":{"amount":"+0.8715149","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941440$82D12D12-16C5-4203-A36A-23C74DC659BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5135fe1df5bb8cf427f2321dc06fb8cb739db46f","datavalue":{"value":{"entity-type":"item","numeric-id":1849988,"id":"Q1849988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6229b563eae012c3faae285cf8b88fa427b3bb0d","datavalue":{"value":{"amount":"+0.87095284","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941440$762C8D77-88E1-4392-A87D-BC04BEB4754B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddb9828d0715f13cbf3144314dde1952285664be","datavalue":{"value":{"entity-type":"item","numeric-id":4260050,"id":"Q4260050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2528a62fe296a57dad927e17271dbc77d1c3a8ee","datavalue":{"value":{"amount":"+0.8706218","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941440$049F33E3-FF8B-47A7-9F02-F14B56B15B29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51015a08d27df38b05ba8c50a5c0533b18619368","datavalue":{"value":{"entity-type":"item","numeric-id":2637125,"id":"Q2637125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25968508f091a73f1e9c5b80cdb18e7168c7ba00","datavalue":{"value":{"amount":"+0.8702913","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941440$20F09EB9-1F90-4FB0-AB12-9F843368A430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48de8af44e9779f8e4d04158d14784ca36b819a0","datavalue":{"value":{"entity-type":"item","numeric-id":3152491,"id":"Q3152491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43269b518aae8801d4ad7310d42f07122c175300","datavalue":{"value":{"amount":"+0.86917984","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941440$17F1D9B0-655B-46A5-9BFE-A38B0589ECF6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3838d4bcb533d2a27ea4a088a84a95ddf6d5892b","datavalue":{"value":{"entity-type":"item","numeric-id":6769178,"id":"Q6769178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941440$1FF346AB-1B7D-4F59-858F-3EEE51226551","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5941440","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5941440"}}}}}