{"entities":{"Q783692":{"pageid":785541,"ns":120,"title":"Item:Q783692","lastrevid":64304067,"modified":"2026-04-11T18:57:43Z","type":"item","id":"Q783692","labels":{"en":{"language":"en","value":"Sorting can exponentially speed up pure dynamic programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7227692"}},"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":"Q783692$6478266D-FD8E-4F7A-9699-6EC5DFD7FA7C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1d95463edf17ed09a2e767276373112c4922830f","datavalue":{"value":{"text":"Sorting can exponentially speed up pure dynamic programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q783692$57A2DC36-0AC1-4713-B624-2D66568EEE1E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f8b15f6a7e8edb8f1e56231017218db8c96efbba","datavalue":{"value":"1441.68305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q783692$CBDA0BB8-50AB-415D-8C02-1602B0395157","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c335a74e7d0453ff4b2102531956594086d933a9","datavalue":{"value":{"entity-type":"item","numeric-id":783691,"id":"Q783691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$A7AB6541-8DE0-4A2E-834B-A875C24DEC04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b70e9e77e4f1b064cc378d54dc586dac5f1d3270","datavalue":{"value":{"entity-type":"item","numeric-id":1109753,"id":"Q1109753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$2985159B-BB33-4932-A8AD-F239801406F7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$0FDF8F66-E451-44AD-ACE2-59E6F6A6A44D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"06f9268330469059a0e033058bcd9bd979095063","datavalue":{"value":{"time":"+2020-08-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q783692$CC39D76C-D0AD-472D-BA8E-6D9358C33BBD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9dc6bed6f84251dab91c575b89c4c684b1ce4e7f","datavalue":{"value":"https://arxiv.org/abs/2012.12838","type":"string"},"datatype":"url"},"type":"statement","id":"Q783692$71F2FA97-38B9-42E2-9F08-9BE06CEC63EB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q783692$7EEDDE32-4BB3-48C4-97CC-100EA139D523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q783692$557646FE-1C05-412C-A630-19EFBC5DE124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q783692$718B7028-8F84-42D3-B9E1-EA4F35CE2589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q783692$3BDC3718-B15E-425D-A455-D9FD6DDB63A0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1e257586266da91799c9832f03855fadbc292cc6","datavalue":{"value":"7227692","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q783692$2D47B5D3-6CE7-4CB8-AAAA-096B7BBBA26A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q783692$B41B2516-9391-4D0A-B4E7-8D5A04FC026A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c40e26d68e487d92ab10d9df0f4cfea5da32927","datavalue":{"value":"MST problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q783692$81E50C17-14FF-4998-8707-F51D632EE2E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q783692$8E09B523-E853-40D6-8AFD-3B21A7E9A239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q783692$D0E665D6-210B-42A5-936F-A66A71502578","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"1412ceb6c71a23f10e8f7e008bf034264afa1496","datavalue":{"value":{"entity-type":"item","numeric-id":41444,"id":"Q41444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$EBFABE25-9233-4547-B593-BD306E43361A","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":"Q783692$39D40794-B49E-4A01-ADE5-446D8F31D1B0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a31489cd9f3902d1c10e7b0a726bbf07e037ac6","datavalue":{"value":"W3015963488","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q783692$8E54C9EA-F830-4580-9581-4B062662C6C9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"061885fa573451da1302a78a271f913f69225f7d","datavalue":{"value":{"entity-type":"item","numeric-id":3249327,"id":"Q3249327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$D171250C-87B5-42F1-85A1-DEBD685F6D4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2e23d3b73f098eb67d4ecbedbc06122ddc75124","datavalue":{"value":{"entity-type":"item","numeric-id":5636923,"id":"Q5636923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$9108F902-146D-410D-8419-18F310D576DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33feed4111c984a5432f7a806f4137f438528fc1","datavalue":{"value":{"entity-type":"item","numeric-id":5963078,"id":"Q5963078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$ECAA6435-7798-441A-AF7C-2EF47706C8E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbad4944f17afff471966f84ddba81383864ae6","datavalue":{"value":{"entity-type":"item","numeric-id":3292045,"id":"Q3292045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$B7FD3B70-FFAA-4274-9FB3-B2D37CDBB653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04f53a44e60807517a77c3256c6fa193f666dfdb","datavalue":{"value":{"entity-type":"item","numeric-id":3945585,"id":"Q3945585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$3DFB8563-AC08-456F-B3F0-DD9B3B6EBF15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e8341661b4a86a1a97589996d589917e5d914ee","datavalue":{"value":{"entity-type":"item","numeric-id":1628699,"id":"Q1628699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$A1FDD8D4-7003-4FFF-B156-8E5C7CEAC741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2117054e09e614a7a81e86cf8f22f23a4fea12ba","datavalue":{"value":{"entity-type":"item","numeric-id":5654074,"id":"Q5654074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$983A6609-1336-49B1-9AA0-0FC40C6BF209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91f1f1685b0394c9eb725ce998d22accbbf88aeb","datavalue":{"value":{"entity-type":"item","numeric-id":1853065,"id":"Q1853065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$F7584B18-1E41-4071-934B-0CDC25D0BFEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e590f27752ee20f0001ae54a0e1d2dccd14985c","datavalue":{"value":{"entity-type":"item","numeric-id":5527519,"id":"Q5527519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$61DA17F9-ACE9-4299-9111-FD82825E3D34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6315d9cda93162c2aba33a1d3e5ec00f12fd74a","datavalue":{"value":{"entity-type":"item","numeric-id":5729523,"id":"Q5729523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q783692$424A7EC4-EA92-4F40-BB9E-BD02D0DF4510","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"32bf46b61fba473a5d0b131caa96c170a717a091","datavalue":{"value":"10.1016/J.IPL.2020.105962","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q783692$6192129B-72E5-499B-9E8B-BA141B120943","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f84dd28ebc8375b32e499128431694732868bbf5","datavalue":{"value":{"entity-type":"item","numeric-id":1628699,"id":"Q1628699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7632999d3762905ed6c68b7ee9cbd3334b2c6216","datavalue":{"value":{"amount":"+0.8459829688072205","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":"Q783692$3FC741B6-F885-43E8-8AB9-2F64C4DC5356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9f0e2c5c15ad9b31e6d62a88dde7682782507e3","datavalue":{"value":{"entity-type":"item","numeric-id":5216795,"id":"Q5216795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c07c62ab98f016adb9074eace7ca4b50178e49d","datavalue":{"value":{"amount":"+0.7471467852592468","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":"Q783692$1BB7382E-55B3-4416-BEAF-90AB28FC1396","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"893dff76fc1508e6758f7cdfee27dd3626965e4c","datavalue":{"value":{"entity-type":"item","numeric-id":5443508,"id":"Q5443508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58bee18560738ee7d57e1c61bee081f3b76b6370","datavalue":{"value":{"amount":"+0.7389028072357178","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":"Q783692$B42BF466-2A48-4B86-80B0-E1498C789858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e263286bbf039d7bccee334d74f5434e48b9dc7","datavalue":{"value":{"entity-type":"item","numeric-id":3743144,"id":"Q3743144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e92a943c8d8da837debc55af4a4d2d40b317e9d7","datavalue":{"value":{"amount":"+0.7375438809394836","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":"Q783692$A3B00AB9-B41B-44EA-86E6-EBB63EE1C90D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9dc1c79a7aab7822737ae3cf54f6b613360a4a0","datavalue":{"value":{"entity-type":"item","numeric-id":547305,"id":"Q547305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fee7c85fe6681649d77dd1e1fae8c7163562fbe9","datavalue":{"value":{"amount":"+0.7311350107192993","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":"Q783692$0C92CB62-C6F7-4D01-9D1F-53F6E64E292C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sorting can exponentially speed up pure dynamic programming","badges":[]}}}}}