{"entities":{"Q2428688":{"pageid":2439431,"ns":120,"title":"Item:Q2428688","lastrevid":73402506,"modified":"2026-04-14T15:47:52Z","type":"item","id":"Q2428688","labels":{"en":{"language":"en","value":"Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6028443"}},"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":"Q2428688$DD03050F-BB79-4CDB-AE58-B09326BB8FBD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c5effa9736e05685d23ac2ee32d6f3b368d4d337","datavalue":{"value":{"text":"Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2428688$B679C64A-8E5F-45BF-B247-EA6BECF98D56","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5091abc6f1ee015b99661bfb3116cf9a9f92b477","datavalue":{"value":"1237.90189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428688$62EDF133-9F77-4843-A1FA-BFD3BD8771B8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be80591c051f16156a6b77af6a7019b70533cbae","datavalue":{"value":{"entity-type":"item","numeric-id":367156,"id":"Q367156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$C1D79DB9-0EEF-4775-9BFF-926388A3B7C7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$BE83B0A0-C03B-45AE-9540-98C544F351FF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"52b04daa1d703ea977748e4d42defef3819c2dd9","datavalue":{"value":{"time":"+2012-04-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2428688$55C756B1-5E57-4461-892F-53B13C491A93","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428688$4B89F2C0-3CE7-461E-8C74-230236655538","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428688$71FF53DE-7833-44C7-8D12-272CCF9C1FC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428688$F904D0B7-3AEE-4E5C-8D77-53862361A1DA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"75051d61a396076942c35986fc56ff4c06205de1","datavalue":{"value":"6028443","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428688$4A44EF7E-01B7-4CA3-B9B7-245E8DF80DB0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428688$02586B23-6579-434C-BCB2-F6BB630395BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a65cc46adc318e4042bf16d3974c1ef4b35a8e98","datavalue":{"value":"combinatorial optimization problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428688$3FF89A49-5337-4101-8161-39EC5A54D2C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95537810381bd01fb1070c58b99d1adf9f8d4c48","datavalue":{"value":"monotone arithmetic circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428688$25606DA2-B4FE-410F-98AD-2376794A702E","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":"Q2428688$F60BD99D-24C9-49C0-9203-6547F360FF86","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6bfa86bad4c73e933bc95554fccf442026ef15f2","datavalue":{"value":"https://doi.org/10.1007/s00453-010-9475-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q2428688$2653A5CF-D618-4A9B-86D7-403A2E21C9A5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"447fbfef2f225d3a19d16ee8780056ad22aaed2d","datavalue":{"value":"W2146843586","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428688$F596C1E5-91CF-4908-AC36-1EA576169FA6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$9E6CF669-7385-46DE-B71F-6E23E45CE106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3df499f57db6ea2558ea92ba2027ece7930c8d74","datavalue":{"value":{"entity-type":"item","numeric-id":430838,"id":"Q430838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$51708984-6097-4D08-BB1F-EF14B7D22DAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2ca77c77da9ee11bcf24f059510cee8234cb30f","datavalue":{"value":{"entity-type":"item","numeric-id":2884495,"id":"Q2884495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$564E4DE4-4EA2-4B96-9EC9-2AF5F32238B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdcd0df9d6668aedd3d91cbe81bf70156bf472f5","datavalue":{"value":{"entity-type":"item","numeric-id":3596368,"id":"Q3596368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$9589F0B7-15C9-4661-A02E-5D5B508129E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52a0d4c7d4224b68e919945a32f9fee4f6b1e9ee","datavalue":{"value":{"entity-type":"item","numeric-id":5926262,"id":"Q5926262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$DFADEB47-3DD9-4EF2-B097-41585BEA5138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60cf26ae066667600df09e7925abede5ecb143a2","datavalue":{"value":{"entity-type":"item","numeric-id":1762982,"id":"Q1762982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$68935526-B5A0-40D7-AFB1-B0CE3F126629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33c266b6c77a64db0e80774d085cd14c5e473c84","datavalue":{"value":{"entity-type":"item","numeric-id":547305,"id":"Q547305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$7CEC39A5-D666-4FE2-B937-FE44CEA21731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9194e9b150f8488fef979658da21ddd0e60751fc","datavalue":{"value":{"entity-type":"item","numeric-id":3651735,"id":"Q3651735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$77D84C87-D620-4371-BAFB-84805F41861C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5009df9c2650d54601861f947f8157b16561e492","datavalue":{"value":{"entity-type":"item","numeric-id":1575073,"id":"Q1575073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$8BCF487A-88E0-4113-A774-E1C35C414567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9539532d16bcb82516fae2db58a1eb7e9c6ca7b","datavalue":{"value":{"entity-type":"item","numeric-id":5538132,"id":"Q5538132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$8C8D1744-8918-4230-95D8-3653E356FB91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$E76ABD32-BFB8-43A8-B423-985FF52A0741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50d47a468645e5fa66ecb8139701c17c6014b12a","datavalue":{"value":{"entity-type":"item","numeric-id":4770206,"id":"Q4770206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$823F3AED-8A45-458E-BC41-CE3D1975F325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efcbeed35653bb79abd91537419405343c057f8f","datavalue":{"value":{"entity-type":"item","numeric-id":3069905,"id":"Q3069905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$D39F1FDD-5AEE-4CF1-B144-C2A8B1FB72ED","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":"Q2428688$97DF727F-0E47-4340-A614-E0A83F8E8170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40f34823cac176489a74f3e54ebb7fe9577d93ab","datavalue":{"value":{"entity-type":"item","numeric-id":4372917,"id":"Q4372917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$3B33E03F-B682-445A-9AEC-DA343452FA04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"677d2035ed2471f26ee7d220e2bbe84e09871f17","datavalue":{"value":{"entity-type":"item","numeric-id":4340685,"id":"Q4340685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$44E07780-8E9A-4688-A677-0D11CD754047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$EA4B8F53-9485-4111-93E6-4B131CFE5268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e873dc563373f6904d1fc7069f448c499a62f8f","datavalue":{"value":{"entity-type":"item","numeric-id":3776614,"id":"Q3776614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$FC912289-F199-44C3-9E37-E03102498EDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52d686fcce39506453772d0734bb9fa8b6c0000c","datavalue":{"value":{"entity-type":"item","numeric-id":4175068,"id":"Q4175068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$1BDFAF18-2955-4A41-95F5-D3D0888D6A60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9a9afc359b780cd186090b621d8dfe3fd08677f","datavalue":{"value":{"entity-type":"item","numeric-id":4196266,"id":"Q4196266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$E03240A7-EF09-4448-A137-6DD70F7A1B38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4908d98c502afac1b40bbe1aa8b2003555524b9","datavalue":{"value":{"entity-type":"item","numeric-id":4427320,"id":"Q4427320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428688$2147B62A-D56E-4ECD-A98D-3ADF413E203B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ddabfbe794978aa6ce311d4b240e19badfc242fc","datavalue":{"value":"10.1007/S00453-010-9475-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428688$79E93B00-2FE7-4C09-9FBE-CBE56FF5A5C6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d135791b4236065ad3c96e0c848b72d04823abd","datavalue":{"value":{"entity-type":"item","numeric-id":517805,"id":"Q517805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29ad7f631045970ec66a6e186876f47401efa86c","datavalue":{"value":{"amount":"+0.7715585231781006","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":"Q2428688$E008C380-956D-4527-B0F4-9624350CCF36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64f0f8f3d8afe4ed7df16b64d64f0dc6a666703d","datavalue":{"value":{"entity-type":"item","numeric-id":4725745,"id":"Q4725745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3314ccd95e1e27e1d1739faac29b61f740093a12","datavalue":{"value":{"amount":"+0.7403628826141357","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":"Q2428688$22E905E7-4027-43D7-91F2-97D7914F1A5E","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":"0b6622bca4cf813635607668769d4f53983abdf2","datavalue":{"value":{"amount":"+0.7316905856132507","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":"Q2428688$6F0D8316-63D2-42EF-B914-032D965C1790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a39df56069dd77efc10bfb1e5a29ff036e9e5f60","datavalue":{"value":{"entity-type":"item","numeric-id":2832574,"id":"Q2832574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"558076c9b8666ff57ae56175a81e121b547d1a24","datavalue":{"value":{"amount":"+0.7295011281967163","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":"Q2428688$C16C5E38-F531-4557-87F0-5A457BF1D498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e4bae74ae89ababd23d4b58b3e7ec9206217cea","datavalue":{"value":{"entity-type":"item","numeric-id":2796404,"id":"Q2796404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f08934bcf7bf6cfc332e7ba6ef363f9e1f89203","datavalue":{"value":{"amount":"+0.7234025001525879","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":"Q2428688$5ED4B5D8-67BC-45FF-8C3B-A2D8C7CC0689","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Exponential_lower_bounds_on_the_complexity_of_a_class_of_dynamic_programs_for_combinatorial_optimization_problems"}}}}}