{"entities":{"Q4601874":{"pageid":6631457,"ns":120,"title":"Item:Q4601874","lastrevid":58295037,"modified":"2026-04-04T14:53:13Z","type":"item","id":"Q4601874","labels":{"en":{"language":"en","value":"Time-approximation trade-offs for inapproximable problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6829363"}},"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":"Q4601874$C5EEF57D-A093-4C87-B0CA-C5FDD52D157B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9076df649366f5ccbefa6459b5f7951723158338","datavalue":{"value":"1380.68441","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601874$BB098A07-C34F-4EA0-8FA0-C8B905958CE8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ffc9ab64882a7f9515eb87005caf9401aaf99b8","datavalue":{"value":{"entity-type":"item","numeric-id":307767,"id":"Q307767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4601874$7330F86E-0E7E-4541-B8EE-116DC14FFCC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7565b924b7d0322100d1a4b4e7f7c011486fd273","datavalue":{"value":{"entity-type":"item","numeric-id":392020,"id":"Q392020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4601874$4C8D14D9-F4F0-4E0C-8996-7ECFC230012D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"704cea475e2d3cbf7f9b1e09c1add901045357ec","datavalue":{"value":{"entity-type":"item","numeric-id":218830,"id":"Q218830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4601874$0960DF29-FCD7-4DB1-B2A0-106A49FA98F9","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":"Q4601874$EC1CFE9D-4E21-4F51-A8F6-07FCC44E0427","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6898c7bfdeece03e42349b789f9b8701d933b05b","datavalue":{"value":"https://arxiv.org/abs/1502.05828","type":"string"},"datatype":"url"},"type":"statement","id":"Q4601874$086C9715-2A77-41D6-983D-1786430B6E19","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601874$262DB2C8-0A5F-49F3-AF48-F2D0AF29D0BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601874$09C6FE46-FC20-4A69-A6AB-59B3E9DDB25A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601874$A646C197-2252-4B30-8247-14529171C7EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601874$F602652D-7697-46D3-8382-C20E885F995F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8878ff75a678a80d86b3cb769244f4ddcbdb1337","datavalue":{"value":"6829363","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601874$5D50685B-04C8-4BF5-B768-258BCE2FE7C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601874$22A8EF76-24B7-4865-B491-ADE9687A5B48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601874$34437E98-9AC5-46EF-9927-CF7F2F82C25E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1c7c178bf1c7f35ae219fa5c07af16c9e2a4621","datavalue":{"value":"polynomial approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601874$F293B6E4-0CBF-4A31-B65C-E0399CAC5C24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4eb28e2c1476319dacd069e5374d918582b9667e","datavalue":{"value":"subexponential approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601874$1139DB92-0580-4610-B0F0-849E81FE1243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfc1c912dbc1f534d35dfe4c7b828346e80b5fd8","datavalue":{"value":"reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601874$E0E13F86-FF6E-4F05-9174-B1F375A93B28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51f95efbd0445c23f397467c5e509da28dd67bbc","datavalue":{"value":"inapproximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601874$8DF95EAA-2A64-4281-A1CB-815D6B121E31","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":"Q4601874$FCA7F82B-199B-4C76-9436-C21450200472","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ee4425836da90bde00ef0c3bf4f880bd35ce2269","datavalue":{"value":"10.4230/LIPICS.STACS.2016.22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601874$2CB9EEB0-80D6-4F29-A5FF-B042051405CE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f87ca807868de30a05ca9305fc0fb02a796a163e","datavalue":{"value":{"entity-type":"item","numeric-id":1678175,"id":"Q1678175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"302ca8a3c49e2f18ec1731299d41ee6d3519caf9","datavalue":{"value":{"amount":"+0.9739397764205932","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":"Q4601874$D9BD5188-525F-4F94-86D8-973761135CB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"356e1d863d2975cf274a1c70742edbf56bb3f1bc","datavalue":{"value":{"entity-type":"item","numeric-id":2051849,"id":"Q2051849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2724130ad7abecf661e06d6823f867cbcbabdd91","datavalue":{"value":{"amount":"+0.802206814289093","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":"Q4601874$AC829E42-C7A8-4196-B5AE-1064E9915B60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5f4dec651b9c476ebac6557c7855f47aaa37ff6","datavalue":{"value":{"entity-type":"item","numeric-id":2272598,"id":"Q2272598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3c24189092600df23f2c74122eafae289244812","datavalue":{"value":{"amount":"+0.7809112668037415","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":"Q4601874$CF08937E-0733-4B18-8E51-D52B20AE43C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"930cdf2101ddc8702488aa529bcbd56e5045800c","datavalue":{"value":{"entity-type":"item","numeric-id":989538,"id":"Q989538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c477f6b09d7f78bcd12b0c523c616561e67db3f","datavalue":{"value":{"amount":"+0.7765246629714966","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":"Q4601874$6E0C5187-AE86-4064-B209-790C10AAF8AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2786f2a6a45dbd1b972df579ad4aee824a0963a","datavalue":{"value":{"entity-type":"item","numeric-id":411835,"id":"Q411835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98cf98ac9df67b8d68e45a861cfe6ddc82d9ad5d","datavalue":{"value":{"amount":"+0.7704424858093262","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":"Q4601874$B3C10A90-974B-4291-9231-0354736CA8F1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4601874","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4601874"}}}}}