{"entities":{"Q4601837":{"pageid":6631420,"ns":120,"title":"Item:Q4601837","lastrevid":53000228,"modified":"2026-01-24T00:17:07Z","type":"item","id":"Q4601837","labels":{"en":{"language":"en","value":"On the (non) NP-hardness of computing circuit complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6829285"}},"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":"Q4601837$16891AA6-EEDD-4805-8E67-9F16E047C883","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"03ca7978f40526da08741fca1c90e67c8a0d9c90","datavalue":{"value":"1388.68091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601837$453E0E8A-89E4-447C-A36E-50F0B787DBF9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a61682d0d235b78ded411489b7744f7fe074c643","datavalue":{"value":{"entity-type":"item","numeric-id":2851869,"id":"Q2851869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4601837$11456038-9C72-44B5-AD91-E2770E347A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"78a3ebf267830b34bb8ced5ebe00bd1ba645205f","datavalue":{"value":{"entity-type":"item","numeric-id":937200,"id":"Q937200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4601837$7C4BCAAA-9971-4FCB-BD39-43D7A4B7ECDF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1335161379199d9038091fb354c2f0e9ba953e5b","datavalue":{"value":{"time":"+2018-01-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4601837$07F278CC-C1BB-41F9-B27D-7A1BF882E6F6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601837$72CDCA9C-9B93-4952-A505-74529D3912EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601837$7C553D05-CA13-441D-8A73-1D7F66BDAC8C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b38c6edc7e5793c25f055ac751e701b261bef4fc","datavalue":{"value":"6829285","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601837$07357CEF-9DA8-41BB-8FE8-3F4EC83A8CD9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d78e5654019584adac44f13a7c02b1ac1c3bfff","datavalue":{"value":"circuit lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601837$A8BFDCD9-02F7-49A7-843C-99636DDE9B8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"531d3028acfe304bf6e6a7883e46a7cdcf7cad05","datavalue":{"value":"minimum circuit size problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601837$E54CAD7C-A602-4CBA-A062-B5A0BAAA3D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601837$E7D0003E-05DE-4797-8E3B-AC0669A2A3F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af61ebf07455b491078594b026930b3701f75079","datavalue":{"value":"projections","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601837$715257A5-5D5F-46AD-8B51-6CC5E1ADB13E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a78b648d77b9a51552964b940d3755d3dfabb55","datavalue":{"value":"reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601837$583CDA25-FB1C-4600-816A-081AEB5111D6","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":"Q4601837$9754AAE4-11CE-405A-A092-A04292B33282","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9cae7856692691d557293852ad9d2d785e0252d5","datavalue":{"value":"10.4230/LIPICS.CCC.2015.365","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601837$0BB9009D-500C-4EBB-99B3-2FB63A93A116","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65ba63261300f459c94e83b4bd43ffd903676db6","datavalue":{"value":{"entity-type":"item","numeric-id":5368903,"id":"Q5368903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f823d0a231ef9a54f7961f1452a01f35ee9e1265","datavalue":{"value":{"amount":"+0.9871452450752258","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":"Q4601837$69A19B20-42AB-4613-A68A-C116B8DAB378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45f241755900fd65cbe38ffcb530ee988db86e8b","datavalue":{"value":{"entity-type":"item","numeric-id":5275370,"id":"Q5275370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74efb9b49c8e85d9a3e4782278c95caabb3c5970","datavalue":{"value":{"amount":"+0.9094261527061462","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":"Q4601837$82A7D2DE-177D-4E29-B69F-E79E839B320C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63c5317f3d03291f322152f958ded8504481b2b9","datavalue":{"value":{"entity-type":"item","numeric-id":5121893,"id":"Q5121893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef825bce3c5f2fd9af391010f12b2393b01d8951","datavalue":{"value":{"amount":"+0.8817058801651001","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":"Q4601837$ED7FBB57-F33C-44FB-B116-4B785D151AA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9b6f924a10373582eba961cac8966edcd4beeb6","datavalue":{"value":{"entity-type":"item","numeric-id":5368752,"id":"Q5368752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b4c9aa7bebf24bc84e1a6b74a7a3ccab26341c0","datavalue":{"value":{"amount":"+0.8783061504364014","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":"Q4601837$F9DB1C32-55ED-4919-ADAF-792F82BE59E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20a22392bf8177b077c5a7b972df3450abcb3b15","datavalue":{"value":{"entity-type":"item","numeric-id":5919681,"id":"Q5919681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bd1ec7db544d6d1404f204d3839e18829d95503","datavalue":{"value":{"amount":"+0.8597921133041382","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":"Q4601837$86EF4077-BD8D-4DF1-950E-445F09CC9D90","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4601837","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4601837"}}}}}