{"entities":{"Q1853546":{"pageid":1864288,"ns":120,"title":"Item:Q1853546","lastrevid":74322126,"modified":"2026-04-14T19:31:48Z","type":"item","id":"Q1853546","labels":{"en":{"language":"en","value":"The inapproximability of non-NP-hard optimization problems."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1857079"}},"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":"Q1853546$3DC51581-9E5E-4A93-ACD5-5C10A8BA03B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0a6a5b01df38c83281ad2499f0a7c210a0bd9ab8","datavalue":{"value":{"text":"The inapproximability of non-NP-hard optimization problems.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853546$C4CDCC03-8CE7-4A17-B518-51FB94922266","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6eb3f49543f2af83773fdf12869f76dc5b73ca61","datavalue":{"value":"1061.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853546$F7FC9962-8BDE-47F3-8C1F-67106EF7EE8C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dffd535d90f7e3b090a8d0582902b87c91b7e9f9","datavalue":{"value":"10.1016/S0304-3975(01)00343-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853546$6DEF4BC3-FD1E-48BC-B084-71595F0E19EC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$5AB5AC51-4187-411E-8D45-B6771733F333","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-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":"Q1853546$2E41BEE2-414D-486F-AC26-26B33950D61F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853546$B1BCD03A-4D47-42FD-AE79-C68E000D37CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853546$0194CCF2-EC26-4184-BE30-42CBACEBD775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853546$275A1C2E-80A3-4D5E-8302-ACE8A36A6640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853546$4559C91F-F720-4222-A85D-154D5DA02AAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853546$B067E863-7121-4C75-907A-16EE5054DAD4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"618b86c467bb06306e2b776d084ac17e8860dea7","datavalue":{"value":"1857079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853546$AF6E551C-EFD6-4B02-92A4-EACC4283520A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da67da54e89e7c80f20f3f95c3ceec18bb927753","datavalue":{"value":"Computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853546$6AF8ED62-6925-4E41-BB3E-453A77A6CA20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d14f568f2791d6c93b5b082a2f0852d39d1f32f9","datavalue":{"value":"Approximation hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853546$D04C36EF-08FA-40AA-AED0-A78113F6A412","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6fd501bec1e4c351a5bb7e183c0156e01d1981e2","datavalue":{"value":"Combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853546$49790BF0-215F-4271-9AC2-958B8F186BAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b73825945a5681262e88060a6d2adc1c13f2530f","datavalue":{"value":"Reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853546$EA8F8A80-4AD3-4A10-974F-6255DD1FBED3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c85847aa6e6c9b2faba8eb113b7d5ac60d95d66c","datavalue":{"value":{"entity-type":"item","numeric-id":529581,"id":"Q529581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$B8AF5785-E712-4221-9D18-FB7D3CA4A545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f371de103517346fec229445823f02e84826a69","datavalue":{"value":{"entity-type":"item","numeric-id":673643,"id":"Q673643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$2C88436F-FC99-4ABD-B5BD-FE4D9C1C8782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"72ce7d9a67faa35e942a183da43448d5f2aacbd9","datavalue":{"value":{"entity-type":"item","numeric-id":557829,"id":"Q557829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$E6BF40C7-0149-4170-8D6C-E4B2819C788B","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":"Q1853546$48997C75-AC13-4785-A9D3-D14472794EC7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7258962f550bf808b8ce0edfe0f9b2099a09d076","datavalue":{"value":{"entity-type":"item","numeric-id":4230322,"id":"Q4230322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$9FE3A538-3FF0-497A-B50F-53FB73D1CDBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46904ca7712e5807737130ff54d9af7fbcef5eda","datavalue":{"value":{"entity-type":"item","numeric-id":4230321,"id":"Q4230321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$99018C59-C2C8-4A70-B273-0BB39EF6276A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5aa2a1ac4e864d41c30b8a828a68a91d18d8ecae","datavalue":{"value":{"entity-type":"item","numeric-id":4258216,"id":"Q4258216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$0C6E2A63-913F-4466-8165-CEF01AA0D91E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"127ecfb8af7bef406c624e706903bb6e0473005e","datavalue":{"value":{"entity-type":"item","numeric-id":5248498,"id":"Q5248498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$DD96FD83-1F92-4D77-BFBA-3340332604D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c6592a49761f461763cc72d2b91dee964ad0498","datavalue":{"value":{"entity-type":"item","numeric-id":1196452,"id":"Q1196452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$67BD198C-E0B2-4D73-B6E5-8A30AA22AD3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63ff92b19145990fc8644b707e05527ac29992be","datavalue":{"value":{"entity-type":"item","numeric-id":4202212,"id":"Q4202212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$E8BD1B6A-DBE3-406C-99DE-4D440D24E9D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6cb60c568207d1b5cadfdaffe5d943f8753f899","datavalue":{"value":{"entity-type":"item","numeric-id":1362338,"id":"Q1362338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$0B992198-1417-4FF1-ABAA-45FC0BFCB1D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df0476b21dfb07e99ff255915d2eb1df03e84bd5","datavalue":{"value":{"entity-type":"item","numeric-id":4337644,"id":"Q4337644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$3ABF7211-87FC-4A99-8F53-F0A86D1FAF2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e317fb43bc2e8a86926776f0f04acc1ab973f72f","datavalue":{"value":{"entity-type":"item","numeric-id":2508336,"id":"Q2508336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$3B11D855-58A9-4B2B-B473-9E898D0D669B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ee0d8e4c28135414cd0564a619e491715231def","datavalue":{"value":{"entity-type":"item","numeric-id":3034815,"id":"Q3034815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$E1D0E1A6-8B11-4DFB-B39D-1D7A8DD1ACF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fa1290987e9e9910315413923140808cd3d7e8a","datavalue":{"value":{"entity-type":"item","numeric-id":4852629,"id":"Q4852629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$0E3E9B75-7E69-497A-88FB-5DA8F5536DC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6e20515d7fb50e98c7d3215121fe76d91ec6609","datavalue":{"value":{"entity-type":"item","numeric-id":4850549,"id":"Q4850549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$6316A033-6004-4C4D-998E-A6D2848F9EF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c2ec98c0fb53a8b469c81cfef3668dc9a2aed9e","datavalue":{"value":{"entity-type":"item","numeric-id":1338895,"id":"Q1338895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$5546EB00-7525-4036-8005-12CBB5D5823C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e22e65c24d1f698f5eb2b3d1bdbc4d2c406f992c","datavalue":{"value":{"entity-type":"item","numeric-id":4259986,"id":"Q4259986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$EF301274-9D9B-473F-96E1-1E9499F78DD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d12760eaf9333d2dcfaea03ce4b42f10d84dc77","datavalue":{"value":{"entity-type":"item","numeric-id":4375813,"id":"Q4375813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$3226AC54-9627-479E-8C96-A48DDE20DFE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$D9D15914-FF36-4FEB-A23C-171C5769CB32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb36ca9ba38f914f8a812b47a78709b0f809e4bf","datavalue":{"value":{"entity-type":"item","numeric-id":1113678,"id":"Q1113678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853546$58A03766-79E0-43CC-8149-7161E9A49E09","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7271bf7671a489d389f5dc407ef0919cc400f8fa","datavalue":{"value":"https://doi.org/10.1016/s0304-3975(01)00343-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1853546$4BBD9C52-86E2-4F08-A720-72497488924D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bbf447e8f9a4aec9a77268f66ddadbb7c9ca012b","datavalue":{"value":"W2062172380","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853546$7FD32791-DEAA-47D4-AA93-058532774365","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"908fad04dfc551c68dd9440837b8ffe2c376d7d2","datavalue":{"value":{"entity-type":"item","numeric-id":4542552,"id":"Q4542552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6420f4a54ebe27cde8e6daa0c8e0e3714ba41b1a","datavalue":{"value":{"amount":"+0.8675363063812256","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":"Q1853546$67D5E546-1D56-48DF-994E-74114EA13B1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91180eda8f021b1a5a7116dcf1d980fd22e7f02f","datavalue":{"value":{"entity-type":"item","numeric-id":4323730,"id":"Q4323730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6420f4a54ebe27cde8e6daa0c8e0e3714ba41b1a","datavalue":{"value":{"amount":"+0.8675363063812256","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":"Q1853546$D7A61AF5-4BC4-4695-BEFE-9304EC14DDC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29f1a1ccf4c1bfe4b8fbb79bcc8627df209f2b95","datavalue":{"value":{"entity-type":"item","numeric-id":4230322,"id":"Q4230322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be30f44ff8386c40f58f48b6c39f095a601787bc","datavalue":{"value":{"amount":"+0.8337910175323486","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":"Q1853546$6A407B87-BCBA-4806-987D-882446EEF740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"800fa30514a24f8fec61c4d7fc3353cc17601ef2","datavalue":{"value":{"entity-type":"item","numeric-id":4864960,"id":"Q4864960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e78a2edcfeaec5b6e064c1b348290bd9b4891af6","datavalue":{"value":{"amount":"+0.8326433300971985","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":"Q1853546$C6181B53-F5A2-4C18-AD26-97A75B971CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f154465087b074874b8b3ba81ee1aa3deab47c1","datavalue":{"value":{"entity-type":"item","numeric-id":5691296,"id":"Q5691296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54248d484446b9e672b23f7078b1f5cd5a9e1335","datavalue":{"value":{"amount":"+0.8278142809867859","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":"Q1853546$E620CBAC-1877-4389-BAA8-8D5A7E424E03","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The inapproximability of non-NP-hard optimization problems.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_inapproximability_of_non-NP-hard_optimization_problems."}}}}}