{"entities":{"Q5919681":{"pageid":8051455,"ns":120,"title":"Item:Q5919681","lastrevid":93385142,"modified":"2026-06-05T04:18:39Z","type":"item","id":"Q5919681","labels":{"en":{"language":"en","value":"The non-hardness of approximating circuit size"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7121052"}},"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":"Q5919681$C862117D-D1AC-411E-B515-9B447366A4CD","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":"Q5919681$48BD17F7-DD14-470A-B829-F4A541D42A69","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6783f13636eae43f98de31c6791b5dcac3aea115","datavalue":{"value":"10.1007/978-3-030-19955-5_2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919681$8DB2D4BF-49CC-4C8D-92F2-24906C07091E","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":"Q5919681$EAC3F400-EDA6-41D9-B0A2-C06D7D316996","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":"Q5919681$F47AEBC5-B9B4-4C51-B236-B30D8E099548","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":"Q5919681$FEAD57AB-B7A8-4507-8A73-C8C074796BF0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"41df48044034ceb6ef08b66017467a62c3d265aa","datavalue":{"value":{"entity-type":"item","numeric-id":2907481,"id":"Q2907481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5919681$A5A12430-2237-449A-9851-A7F715FDA83A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"57e80c845c96b0988db493e5ae271fe0a944be8f","datavalue":{"value":{"time":"+2019-10-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5919681$731736EF-7DDA-4AE0-8F1A-C23746DE0161","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":"Q5919681$06ADB80F-0F69-4968-B63D-9815851BD2F7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919681$E2409649-44D6-461D-8CCF-A411ADCF5F08","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e86a0b10b4b9e017acc8d25770ac14839b8b0bac","datavalue":{"value":"7121052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919681$B62125C4-AE00-4A1C-9CCB-F6B81779A130","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5919681$18D9C1BA-4A88-45C5-A078-28D99178FE7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"510d7db7eb68c662207d3888ebc972124bf71406","datavalue":{"value":"Minimum Circuit Size problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5919681$AB5380B4-F268-42DB-8BB7-6257B8C4D500","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a78b648d77b9a51552964b940d3755d3dfabb55","datavalue":{"value":"reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5919681$BBC5108A-8F3E-4E5B-AF9F-0478AF0CB1C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75d5876ebcd43299e86a8e75d42a084c87f8f56f","datavalue":{"value":"time-bounded Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5919681$826D452F-BC96-41C7-81F7-753805978391","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":"Q5919681$90AEAD08-F7BD-4892-A4D9-AB4460BD9D86","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fd3665c4d235aee0b45b9cefa3401a9c08f76947","datavalue":{"value":"W2902479036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919681$9640B209-BAB0-4E69-ABD9-684156FF815D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"150ac691ae3360a7fbec6f0521316b614fcfe592","datavalue":{"value":{"entity-type":"item","numeric-id":5918358,"id":"Q5918358"},"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":"Q5919681$0D89F5FC-3D0D-46FD-A637-3B3669E5BAD2","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":"cab3a93f6f1178db8980a0f3faeb445a8143fb56","datavalue":{"value":{"amount":"+0.8969948291778564","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":"Q5919681$0635E706-303B-46D0-8097-05D9679A50F3","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":"765612ab684aae8b7732182e91f48258a89200ce","datavalue":{"value":{"amount":"+0.8900211453437805","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":"Q5919681$B2AD9207-D518-4B99-9011-4E0AE9F0D85F","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":"09fd50ba989df1d8a4eafb02350fd25b86d44e01","datavalue":{"value":{"amount":"+0.8688225746154785","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":"Q5919681$E797F693-EDA6-4D31-B918-D1DCD5F18F99","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":"dc9dba5d52e737916ad0edcc42f16e8ae4017970","datavalue":{"value":{"amount":"+0.8672471046447754","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":"Q5919681$09EAC028-573B-4B97-B8A9-D205E32FFFDA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The non-hardness of approximating circuit size","badges":[]}}}}}