{"entities":{"Q960453":{"pageid":962301,"ns":120,"title":"Item:Q960453","lastrevid":65658027,"modified":"2026-04-12T04:06:25Z","type":"item","id":"Q960453","labels":{"en":{"language":"en","value":"What makes an optimization problem hard?."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5475570"}},"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":"Q960453$3BB1EC4F-A039-4BD1-8B2A-D15B4EA494DF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3f5a224b6868b861fb4c83f19fc88590a6dbaf73","datavalue":{"value":{"text":"What makes an optimization problem hard?.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q960453$2DE64C08-0BC6-4147-9820-21C2B50E3F60","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02c53ab30d411b84fdd02bf9922e8bb34da22b83","datavalue":{"value":"1455.90156","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960453$08B9FFB2-2D7F-4440-B4E5-62FE70F32653","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8787339a86f3b90dde461740f4093e02e1684ce","datavalue":{"value":{"entity-type":"item","numeric-id":331394,"id":"Q331394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960453$75F3C531-7375-4665-99A5-A180B96E598C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a0ec07d3b4d3052c844f95151a6aa39ac6ae457b","datavalue":{"value":{"entity-type":"item","numeric-id":280677,"id":"Q280677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960453$DA77ED88-E40A-471E-A806-AF7D6642F0E0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1dec05d6eca21826ddc25d78a5bfbbb3575f964c","datavalue":{"value":{"entity-type":"item","numeric-id":86231,"id":"Q86231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960453$D96D8678-3C34-4390-9D1B-5DC096A372D5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5e585f09c3e724b05f201668ef36e38cb4b3cf3a","datavalue":{"value":{"time":"+2008-12-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q960453$B102089D-C9CD-41AC-8A0B-00C8D94C2680","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ef473c570c084859ad9b1497d468614a397afb1d","datavalue":{"value":"Summary: We address the question: ``Are some classes of combinatorial optimization problems intrinsically harder than others, without regard to the algorithm one uses, or can difficulty only be assessed relative to particular algorithms?'' We provide a measure of the hardness of a particular optimization problem for a particular optimization algorithm and present two algorithm-independent quantities that use this measure to provide answers to our question. In the first of these we average hardness over all possible algorithms and show that according to this quantity, there are no distinctions between optimization problems. In this sense no problems are intrinsically harder than others. For the second quantity, rather than average over all algorithms, we consider the level of hardness of a problem (or class of problems) for the associated optimal algorithm. By this criteria there are classes of problems that are intrinsically harder than others.","type":"string"},"datatype":"string"},"type":"statement","id":"Q960453$49878127-3F52-4F80-858B-4E90A1906EC3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960453$1EF26343-BC97-40C4-AB5A-30087D43FFCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960453$56C6F509-ECD5-4B89-8CA7-3AF7ABFA5581","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b8a5bbedfffb34705f9a80d24a0519c92ce08e63","datavalue":{"value":"5475570","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960453$19738344-0526-49C3-914D-8FAF7C4BDCDF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q960453$46DD1464-2DEA-48D5-A963-0E9391DF81D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b6fbaa665d2c2987e08bc6dbe57daa649ae0960","datavalue":{"value":"optimization algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q960453$1749A6F8-17E4-411A-91A0-7789E0A5538A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4881dceebcfc2cfaaf48b0eeca275f318bc3a7ae","datavalue":{"value":"hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q960453$3259E64E-E527-4E63-A8CD-DFDD11029AEC","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":"Q960453$72B4CEB4-F3F0-4E70-8981-3F8E30574614","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"88d7ea3f6dd58108348130ef7660fea67c44d55c","datavalue":{"value":"https://doi.org/10.1002/cplx.6130010511","type":"string"},"datatype":"url"},"type":"statement","id":"Q960453$B2FA3D29-5697-48FA-A183-CF48999D9FFC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1e653bb9404d29d7abfb387323cfdea0eb2ee6a2","datavalue":{"value":"W2279189561","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960453$1ECC7CBA-4E35-4BBE-B0FE-0DEC959F8CC5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4ca0d0a990c7f81b07717aca687cb01a7da2dd94","datavalue":{"value":"10.1002/CPLX.6130010511","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960453$F53999A1-FA0F-4581-BCE2-E9207DB80A7B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b587b9c0e467818816b1303b3d262203b7a3b3a0","datavalue":{"value":{"entity-type":"item","numeric-id":1762054,"id":"Q1762054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"157834e58b9575ee44a1e64719bc2cb9b2610aa1","datavalue":{"value":{"amount":"+0.7781065702438354","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":"Q960453$2F8C2767-5F2A-40B3-B3EB-B5DF5553D93A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a33bb1713eb71833beaacb0f8553c8951fc25d8c","datavalue":{"value":{"entity-type":"item","numeric-id":1107309,"id":"Q1107309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beadf2bc3a38158faebc16d1e527ec0f3d81418b","datavalue":{"value":{"amount":"+0.7693182229995728","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":"Q960453$C5661820-F1BB-4434-880C-CEC8D2D9E3E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3c555a9b5d6827d85f79e3aa1a59d4a9bf6cd3b","datavalue":{"value":{"entity-type":"item","numeric-id":4649208,"id":"Q4649208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13c03b41487c7a297feea793547709fa082fdebb","datavalue":{"value":{"amount":"+0.7691212296485901","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":"Q960453$8E52F637-BBBA-4137-93BA-205A6E504681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4a762f69b1484ee090ab82f561f790a7faf966a","datavalue":{"value":{"entity-type":"item","numeric-id":2581548,"id":"Q2581548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d17971b1a4aa5e932e2a43ff97dcc9abfca70d22","datavalue":{"value":{"amount":"+0.7590832114219666","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":"Q960453$29151A30-271A-4BA6-AE22-1FB4F5F20067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69aeca3333eba0f357d63c8e2f29a4faf137ff15","datavalue":{"value":{"entity-type":"item","numeric-id":4012216,"id":"Q4012216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14decf775e22f9b289254cc2ad3f31b9ade7f1ad","datavalue":{"value":{"amount":"+0.7499832510948181","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":"Q960453$ED3D24EA-2BF2-41B5-A8F9-EC0153AF1D59","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"What makes an optimization problem hard?.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/What_makes_an_optimization_problem_hard%3F."}}}}}