{"entities":{"Q1813126":{"pageid":1823868,"ns":120,"title":"Item:Q1813126","lastrevid":46147624,"modified":"2025-12-23T13:27:00Z","type":"item","id":"Q1813126","labels":{"en":{"language":"en","value":"The gap between monotone and non-monotone circuit complexity is exponential"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2501"}},"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":"Q1813126$199841FF-BCC0-4D38-B4E7-275F1AB6E202","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e5c5c81b3f4da3ab4f431395d26ca9e3db1402f4","datavalue":{"value":{"text":"The gap between monotone and non-monotone circuit complexity is exponential","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1813126$B36886A8-99BA-43E0-B8A2-E23A458C66C9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"480e0051f7dda7bc60c7b4265b398c0c0d8a052f","datavalue":{"value":"0807.94026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813126$1F5C3369-2CB5-480F-8D56-375C37D52A78","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eb7cb16770db97f84cd15f04697fe6808dae7fa2","datavalue":{"value":"10.1007/BF02122563","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813126$F476EFD1-9D4B-49B4-AFB9-3002A7E3FDBE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813126$1932F73D-5E4D-4BDE-ABCE-496DAE3AC261","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1813126$E6DEDDB5-D2D3-4C48-8FB5-87610E2D11F8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bcbe1d7b1903e5198cb38520b428d18833228637","datavalue":{"value":"A. A. Razborov has shown that there exists a polynomial time computable monotone Boolean function whose monotone circuit complexity is at least \\(n^{c\\log n}\\). We observe that this lower bound can be improved to \\(\\exp(cn^{1/6-o(1)})\\). The proof is immediate by combining the Alon- Boppana version of another argument of Razborov with results of Gr\u00f6tschel-Lov\u00e1sz-Schrijver on the Lov\u00e1sz-capacity \\(\\delta\\) of a graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813126$E3F2974E-93C4-4C79-AF43-B328BEB7A208","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"007f7f82691f1d7656215e5be329d57b0bfdf5e7","datavalue":{"value":"94C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813126$28A3D222-7F58-480D-ACDF-B68B7E3BFA45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813126$FD5F0591-A0D2-41D2-A6CA-F7BB2C6CC7BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c570e860ba389c31488f932c35162b4cfae83a1","datavalue":{"value":"2501","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813126$7AAEF7D8-01C2-47F3-BBE8-CE27314D5916","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f7dde4a423c2580d52c0f36d3743f26c291e5854","datavalue":{"value":{"entity-type":"item","numeric-id":222777,"id":"Q222777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813126$A769C51B-A44E-4440-B13A-07C5C22D8D79","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":"Q1813126$ABF5F64C-58A1-44F9-8CDC-3B14F11F4D06","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2ca04c59b1468ff9eb03a30febcf55d98359908","datavalue":{"value":{"entity-type":"item","numeric-id":1094870,"id":"Q1094870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813126$DFA63BA4-7D92-4728-A956-57EE376A20F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813126$B820E2E1-0D80-42FC-8919-94AF70CBFC42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5800d93eb4f8caa03263f0b51c3001208ff1e9ad","datavalue":{"value":{"entity-type":"item","numeric-id":3050157,"id":"Q3050157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813126$B41F44BE-BEFA-4B82-B3E0-ADB412EB82A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a48c289367846d2e6cbf6ff475cf182266d6c35","datavalue":{"value":{"entity-type":"item","numeric-id":4178914,"id":"Q4178914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813126$801E2391-E479-4F22-91BA-E519431FFE00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0942c3ffeac8339c20eccc6667aba9b8af08cc5f","datavalue":{"value":{"entity-type":"item","numeric-id":3758729,"id":"Q3758729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813126$B82367D8-48F0-48EC-A754-5EFAE9C7213B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14e822d0f6871d5df9de9fd97a15be05d850e629","datavalue":{"value":{"entity-type":"item","numeric-id":1071001,"id":"Q1071001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813126$95F57F19-590D-41D1-B6F4-46C2F2A221EB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d32fb592ac6359c6294580b99c3dc7b920afabb","datavalue":{"value":{"entity-type":"item","numeric-id":3786412,"id":"Q3786412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e031a62eee46641a9292bfe83ccf5a574a7353d","datavalue":{"value":{"amount":"+0.8323892951011658","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":"Q1813126$80727EF4-230C-4389-AA00-840CEF76D149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fee9f6b3f17440c91e0f24f51695441fe81c9fa","datavalue":{"value":{"entity-type":"item","numeric-id":5928586,"id":"Q5928586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca33cfd07c6aa5ea86f4e86341cf652d1255d85a","datavalue":{"value":{"amount":"+0.8014087677001953","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":"Q1813126$6758484F-3D67-4AAA-8303-4D06B3FEAB36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13035691865ae8935425f2404f426833ab6a9d07","datavalue":{"value":{"entity-type":"item","numeric-id":1288204,"id":"Q1288204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"988c527ae390bd5b8730cf2b8cb4a8eae911c972","datavalue":{"value":{"amount":"+0.7899512052536011","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":"Q1813126$21E4E918-21AC-4EB7-A7C5-2F36987285E8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1813126","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1813126"}}}}}