{"entities":{"Q5918358":{"pageid":8049017,"ns":120,"title":"Item:Q5918358","lastrevid":97724054,"modified":"2026-06-05T15:18:00Z","type":"item","id":"Q5918358","labels":{"en":{"language":"en","value":"The non-hardness of approximating circuit size"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7377743"}},"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":"Q5918358$B5C766D8-1EAB-4828-B0EB-8C86A1FBD90B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ed1dd5c6717c94f385815d0993cec6f6b4c9d6ff","datavalue":{"value":{"text":"The non-hardness of approximating circuit size","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5918358$65CDAE53-0BAA-4021-B023-A3F5A771B8EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86eae0bd36f68e0853fe5ab9e6c133a110babb03","datavalue":{"value":{"entity-type":"item","numeric-id":1058525,"id":"Q1058525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$A43472BA-F685-499A-A361-76880015676A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d38426cd3b6298db123a4e7a845890efc6536c9","datavalue":{"value":{"entity-type":"item","numeric-id":1991428,"id":"Q1991428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$7ABC9856-F559-449C-918A-ED24304575AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"deea6bfd086b65f81ba8b6990f58a84d137088ff","datavalue":{"value":{"entity-type":"item","numeric-id":2043878,"id":"Q2043878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$A75FE3E5-4903-49CD-BDD2-354C8DF94778","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$ECED2A0A-B85B-46FA-9E43-A4D59ECD3397","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"49ee50f687aac7f2e200a1c881fd3cbd74f354c8","datavalue":{"value":{"time":"+2021-08-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5918358$CA84E944-0DD9-41C1-9C23-E592DD91925A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"894f5afcfd6d6b61b203c52f449d584a6478cf01","datavalue":{"value":"https://hdl.handle.net/1721.1/133146.2","type":"string"},"datatype":"url"},"type":"statement","id":"Q5918358$0BC160B0-6011-48BF-BCF1-7F8E03A3DCD3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918358$DB8D1553-B84C-4A0D-9294-77B0DEEB6220","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c37fac2c931d67dbbefba0164b27b938be9a6535","datavalue":{"value":"7377743","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918358$4045CD58-1FE6-4DD2-BA8F-0BAB14068E3F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"531d3028acfe304bf6e6a7883e46a7cdcf7cad05","datavalue":{"value":"minimum circuit size problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918358$05269B86-35C5-4AEA-A44A-9188429EA322","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a78b648d77b9a51552964b940d3755d3dfabb55","datavalue":{"value":"reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918358$F72A61A4-45BF-49DD-9099-FB9536FDA94F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918358$19441B05-4B5C-4B14-B3D5-B097FB1D830A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75d5876ebcd43299e86a8e75d42a084c87f8f56f","datavalue":{"value":"time-bounded Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918358$7968F977-DB5B-43DE-B50A-EF2734FC184F","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":"Q5918358$A61E2E6C-9846-4985-97C9-48DFB0F0A5C3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e82fdd160ec086b0a2e50095e0f454df7d28a9a2","datavalue":{"value":"W2955383056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918358$0DFE155B-DD87-44E5-9F12-6A28AC70795D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5d817fcded45c0d7d6169802a7ae39651b45a7a","datavalue":{"value":{"entity-type":"item","numeric-id":1276160,"id":"Q1276160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$2B29021F-5776-4308-9A22-61F457C1EB96","rank":"normal"},{"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":"Q5918358$F792E717-B0E5-4572-9DFE-F44D6064B7C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c60c85fd506e5bb84dfbb86fb8dd2f2d41f1f98e","datavalue":{"value":{"entity-type":"item","numeric-id":2407082,"id":"Q2407082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$232BAC6A-6774-4F6C-A29B-3C5843C04901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30db3a0541a50ae0ef093e974713444c090ff008","datavalue":{"value":{"entity-type":"item","numeric-id":5205823,"id":"Q5205823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$BA629A6B-DB0C-41EE-AE34-C3412B85C1F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e64b458ef05a890f9438b727977f8a82852b2ef","datavalue":{"value":{"entity-type":"item","numeric-id":5470741,"id":"Q5470741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$8818E66A-D149-45B5-B411-2DF4F538CA4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93b77eec5c9c6a43ad6b380ed444f38129edb7d5","datavalue":{"value":{"entity-type":"item","numeric-id":3614150,"id":"Q3614150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$C8E91611-C9AD-41C2-88B6-724F9DAB0FC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77ed0a39ef4db2eafa0124b6371533aa9541e412","datavalue":{"value":{"entity-type":"item","numeric-id":619899,"id":"Q619899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$9F093210-9885-48B2-970E-C047F1D3BBC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fe8314df517c214c8b9b71718259524f7aa4965","datavalue":{"value":{"entity-type":"item","numeric-id":2410683,"id":"Q2410683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$EB450CF1-6A96-4B1D-A471-31405898190A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74076cba76b38a9d319deccc36e39aecfa925a50","datavalue":{"value":{"entity-type":"item","numeric-id":3176189,"id":"Q3176189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$5B289B7F-8D51-46C5-B47E-17669EA53A68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc04138aef4230983fcfb4807c3c0e669d63e6c1","datavalue":{"value":{"entity-type":"item","numeric-id":5919681,"id":"Q5919681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$36914066-7A57-4499-B2C5-01CD551DD5A8","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":"Q5918358$DF96DD18-ED36-4ACA-83BB-A4B7376DAB2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa5257c47b3e16480bc939376f28ea97a5ff248b","datavalue":{"value":{"entity-type":"item","numeric-id":5091223,"id":"Q5091223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$E78B5C95-A113-46BD-B84E-F1DD07E1E702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63223a2b10e799e0a620d9698b0286ebd9668db5","datavalue":{"value":{"entity-type":"item","numeric-id":5441360,"id":"Q5441360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$92EB66CC-5C13-4D8B-8381-630C272839D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf3e49de912aee6985512ce3c0a6befaa143ef44","datavalue":{"value":{"entity-type":"item","numeric-id":5111137,"id":"Q5111137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$950D312E-BE73-4DB2-A296-9A4AB7A747A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c4dce6b115f8f29df6873e3f5cdc159accaecb2","datavalue":{"value":{"entity-type":"item","numeric-id":5368752,"id":"Q5368752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$52BA4AAC-E1E1-464B-BA5A-29E420D2B70E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b9e50b53133d1aaa9b76865d95847db88dc323d","datavalue":{"value":{"entity-type":"item","numeric-id":5275370,"id":"Q5275370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$6E0BEA3D-1067-4845-A2D5-255906C332C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"363bd8e91b96d49826944476ef6d40b0bdd0566b","datavalue":{"value":{"entity-type":"item","numeric-id":5875732,"id":"Q5875732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$076BDB91-F383-4626-BD93-CAC5E20173EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92b73ee66a2d26abdd6413f8f20521710f8f56a0","datavalue":{"value":{"entity-type":"item","numeric-id":5121895,"id":"Q5121895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$97AFBB7F-89D0-46A4-AACF-4973F68D690C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9973175c5d8b59b8a5a43ac3eefc19a8892b7cf6","datavalue":{"value":{"entity-type":"item","numeric-id":3191973,"id":"Q3191973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$E3F56CAB-EC86-48FD-BDE4-E29688303799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6f289e18bd92f285debf80847f6bf6a36fe0084","datavalue":{"value":{"entity-type":"item","numeric-id":5212860,"id":"Q5212860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$795A3113-FD42-403E-8DCF-6775315FD4F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a45ad3d84b830e9fef5d45dc17de33d11ad9527c","datavalue":{"value":{"entity-type":"item","numeric-id":5368903,"id":"Q5368903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$F30D716C-8822-4407-BD5A-5D0C7F8EA777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e80f11fa21e4291494908f8f2fbfdf6dbf3af18","datavalue":{"value":{"entity-type":"item","numeric-id":5111148,"id":"Q5111148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$ECBD7B92-C79D-4A3A-BED9-49500A8E1FCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7015192d3efadcc818414bfa24ced3b0349a225c","datavalue":{"value":{"entity-type":"item","numeric-id":5091779,"id":"Q5091779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$6A62BC88-BE5C-491F-B34F-38192C7826AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"072e91014367104cf566b8b67a728f68b171a4bc","datavalue":{"value":{"entity-type":"item","numeric-id":5906823,"id":"Q5906823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$EFBF6B12-E420-4F0E-B502-E920B314C541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4aee363c3cad143d6bf5ea62c77e20d2a2b7bddd","datavalue":{"value":{"entity-type":"item","numeric-id":2404611,"id":"Q2404611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$E8C0B6B2-6232-4827-A4F5-F380A80A7EC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14efb49139bf6636efc61d26092213d1072148b8","datavalue":{"value":{"entity-type":"item","numeric-id":4779250,"id":"Q4779250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$90E6C102-0DB8-4D43-A23C-60361A0CABC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"624abf0da839d476906101af8b6d74820b65cb0e","datavalue":{"value":{"entity-type":"item","numeric-id":4393484,"id":"Q4393484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918358$CD2BB44A-75B0-4E28-A4EB-50D619059F99","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b0bb734ed74143772ac72e7b225d71afb7085706","datavalue":{"value":"10.1007/S00224-020-10004-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918358$0A9650B5-429B-4FD8-941D-04A94B25B6A9","rank":"normal"}],"P1643":[{"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":"cbc7b084ca2c70520ba982e843b77467166dd61f","datavalue":{"value":{"amount":"+0.9974714517593384","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":"Q5918358$961F0A3C-739B-42E3-8DFF-13F54A26C86B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bc03415ef2c0254f875bba7a346450f806b2fec","datavalue":{"value":{"entity-type":"item","numeric-id":5111269,"id":"Q5111269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c23886c153efc7f06510e0ba9adb0d080048e75","datavalue":{"value":{"amount":"+0.8954219222068787","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":"Q5918358$5E03F3BE-D162-4332-B385-309C39C84A95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f221be79237e59d4229d3740c46c234702967320","datavalue":{"value":{"entity-type":"item","numeric-id":5205823,"id":"Q5205823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcf7b263b091c921ac1fae0fa1644563f9625226","datavalue":{"value":{"amount":"+0.8883750438690186","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":"Q5918358$4E694AD7-0996-4895-B709-18533FC29936","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":"1c4334778e091050314c45b71c3e9178d763268f","datavalue":{"value":{"amount":"+0.8632267713546753","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":"Q5918358$9F383187-6DF0-48F5-A588-55B4CF26EBA3","rank":"normal"},{"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":"7a26002a13711783a62c3ac4a58dd50e0e855c12","datavalue":{"value":{"amount":"+0.8611795902252197","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":"Q5918358$0B5F61B1-1718-4050-83A2-84ABC223DD5C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The non-hardness of approximating circuit size (scientific article; zbMATH DE number 7377743)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_non-hardness_of_approximating_circuit_size_(scientific_article;_zbMATH_DE_number_7377743)"}}}}}