{"entities":{"Q5144987":{"pageid":7174558,"ns":120,"title":"Item:Q5144987","lastrevid":55375750,"modified":"2026-02-17T15:00:31Z","type":"item","id":"Q5144987","labels":{"en":{"language":"en","value":"Unexpected hardness results for Kolmogorov complexity under uniform reductions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7298308"}},"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":"Q5144987$24F40E12-56C9-4E53-BB92-740AAA6FF0A9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2729bca782821293bea8f46cdbc611b898b1835d","datavalue":{"value":{"text":"Unexpected hardness results for Kolmogorov complexity under uniform reductions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5144987$C0034952-D70F-419D-B882-AEB56488AC43","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"683f0ba6fa59727d7e09026cc9ffa995d3cf1f72","datavalue":{"value":"10.1145/3357713.3384251","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5144987$B1772D0F-C1CD-43E6-8F1F-4259A556B136","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a2c9f93dff3981faa30fe20770d6f56b647675e1","datavalue":{"value":{"entity-type":"item","numeric-id":1751255,"id":"Q1751255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5144987$C66B387A-358C-4D2B-8B1C-BF383AEE8E0F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"54ff79ea3bd27e27eed482c87c60ccd48a68f63f","datavalue":{"value":{"entity-type":"item","numeric-id":5144890,"id":"Q5144890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5144987$62F8E7AA-C6CA-4E08-9B21-68C4F9920E5E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a1a70f16fd8e81a4c35439aeec3d3645cd1e55e6","datavalue":{"value":{"time":"+2021-01-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5144987$199CD1FD-1B60-4FCE-891D-8DE42F5D6CCC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5144987$17A207D8-D64D-4B1A-9DAC-E7592469D2B1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fe14c589b3b49eb06973359d0e4c1cd1eaba8872","datavalue":{"value":"7298308","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5144987$05B1AA0C-D4D3-40FC-9CFC-BCC5FFF08CFE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9be3cb5e8d18fb42e25490086bf1c9afa7abc57","datavalue":{"value":"(black-box) reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5144987$D13884D4-7C75-44A0-8B50-0141B76083F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5144987$FE21B5DE-F7E6-4F2E-929F-3437FB2B44C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0539db072e4ee5849e5383c82c9881917950f74e","datavalue":{"value":"pseudorandomness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5144987$F9EEBC42-A4E8-4F21-88E5-4F1BF98F10E8","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":"Q5144987$06BE6C3E-62EE-460E-AF59-665BD9383827","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"41da4cc559793b049db490888904418b9595889e","datavalue":{"value":"https://doi.org/10.1145/3357713.3384251","type":"string"},"datatype":"url"},"type":"statement","id":"Q5144987$4D5907A2-D0D9-4429-99FF-C6751F096A4C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"134776d1bc037ee8fc3c92d73d96c085ec23d444","datavalue":{"value":"W3034183797","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5144987$AF4C830F-EBCB-49D5-92EF-CB597A966DA5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b14904c6c9f5f5269824237686b505c3c223fc24","datavalue":{"value":{"entity-type":"item","numeric-id":5470741,"id":"Q5470741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0d301d89d2ef7ed9f871abacbf3477d6fbfdbfa","datavalue":{"value":{"amount":"+0.861592710018158","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":"Q5144987$67BE79AF-E011-4818-B45E-6FC9DC288214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f14ddeb2af24eaffa0b7ffef04b45075dffea2b4","datavalue":{"value":{"entity-type":"item","numeric-id":6568372,"id":"Q6568372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"043a31e588000c49879e7debfe8130a952ebfb68","datavalue":{"value":{"amount":"+0.852275550365448","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":"Q5144987$23064AE7-7337-4C3E-A718-293B455654DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"620522367fa21c4ef51d754675d83ea58050a76a","datavalue":{"value":{"entity-type":"item","numeric-id":3576206,"id":"Q3576206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c9b30c0ff212d6dd0fe1aa41d6be559947349c7","datavalue":{"value":{"amount":"+0.8391410112380981","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":"Q5144987$CD697D74-6531-4CDF-90D4-225CB370DB46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ba4a41e7348b719c2e25d3f8f0e435c6d241723","datavalue":{"value":{"entity-type":"item","numeric-id":5309733,"id":"Q5309733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"099d98b4ea9f3ba4ba42eff33ae5d17223bd57b3","datavalue":{"value":{"amount":"+0.8326022624969482","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":"Q5144987$3CB27FB7-8B37-4375-A15E-443C67ECBADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f1a60ef39e02fdeb3402174b4aa04a7e284ffc5","datavalue":{"value":{"entity-type":"item","numeric-id":3012814,"id":"Q3012814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75b6aa5d4eff8cedcd46a40c572183b78e60bb11","datavalue":{"value":{"amount":"+0.8272054195404053","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":"Q5144987$9D7A2506-4076-49E4-B1C2-B38ECF91C504","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5144987","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5144987"}}}}}