{"entities":{"Q1894653":{"pageid":1905395,"ns":120,"title":"Item:Q1894653","lastrevid":69213129,"modified":"2026-04-13T05:31:18Z","type":"item","id":"Q1894653","labels":{"en":{"language":"en","value":"The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 782150"}},"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":"Q1894653$2D7DEC33-599E-4D5C-A693-6797254B066F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ecf726116107a1534d363aa65e694952f1335d1e","datavalue":{"value":{"text":"The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1894653$ED718F14-4ABA-41BB-ACC0-F903CF1CC3E0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9c1f5e477db1807a9a06fd70a13107ed43fc7299","datavalue":{"value":"0840.93073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894653$AE5294A5-E477-4050-8F09-7C48A700722F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"15e1c1b564d0eb2864734cdb2e9321a88ee0e602","datavalue":{"value":"10.1007/BF01211520","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894653$097DC228-45B4-4D03-A2C3-9A75FA5C3632","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f9a6fd3bffc36d504b23d1cab089dfd96e8b3cd","datavalue":{"value":{"entity-type":"item","numeric-id":1328065,"id":"Q1328065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$455213E9-A27F-4ACF-88C4-B772B82C0230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a8d1b9af232a0701d50e4a73b3be3acd9617ce13","datavalue":{"value":{"entity-type":"item","numeric-id":1894652,"id":"Q1894652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$2371B53D-0855-4E16-B544-31EB93F0C2E9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"83c55f09dfa869c2dbb8e5587cb9fee3e3fbc7c5","datavalue":{"value":{"entity-type":"item","numeric-id":186563,"id":"Q186563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$979E7AEA-C386-4C11-981D-A7A9BF50FACD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f63f3cd5ea250cae1efb23f4567f6e5e9f7cfafd","datavalue":{"value":{"time":"+1996-07-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":"Q1894653$CB119A1B-0C88-44F4-BAB3-AA9458CB99CC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"197baa53411214765d089ad6dfd21036e1d5a510","datavalue":{"value":"A typical approach to characterizing robust stability (regularity) of an interval matrix with a stable (nonsingular) center matrix is to compute the minimum scaling of the nonnegative error matrix (specifying maximum elementwise perturbations from the center matrix) for which instability (singularity) is achieved. Here, it is shown that approximating this minimum scaling is a MAX-SNP-hard problem. This implies that in general, unless the class of deterministic polynomial-time decision problems equals the class of nondeterministic polynomial-time decision problems (not likely), this minimum scaling cannot be approximated with a ratio arbitrarily close to unity in polynomial time.   As an intermediate step in deriving this result, a class of interval matrix families is exhibited for which regularity and robust stability are equivalent. This is a generalization of an earlier result [\\textit{A. Nemirovskij}, Math. Control Signals Syst. 6, 99-105 (1993; Zbl 0792.93100)], and may be of independent interest in the study of robust stability problems for interval matrices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894653$0A502536-5CD2-4D15-86D2-E7972480AF3D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e1bf42ae8d3e4c2610617cf8c51854b1b4c232b6","datavalue":{"value":{"entity-type":"item","numeric-id":1283331,"id":"Q1283331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$E1AA9837-9177-4D2E-8911-7E2AEB912129","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fc648f2b3cbfd7ca947171669dbba40874dba93b","datavalue":{"value":"93D09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894653$5B8DCF50-10F5-4AEF-840D-3427093C85D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"10e7ae4f3272e1b3be03ffc40fe137c122ddd99d","datavalue":{"value":"93B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894653$9A840DF0-7B20-47C7-9840-1678AFADEE76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dbba85562facd3e546df50a87515dddbb3dae27e","datavalue":{"value":"93C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894653$9116C84C-541D-4C5C-A365-2E16CC96737B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"986235342db4f1c6179879ca093256c98054dbe9","datavalue":{"value":"782150","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894653$757644EE-5240-4491-B2F2-160300AB513D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96c18a7477603b23a2126218e71a474e175afd3b","datavalue":{"value":"SNP-hard problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894653$1E6D2A0F-BBD5-4518-87E5-D5C2191B904E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5764c0aab378f9ceed64d8dec1ce90b387f04bd0","datavalue":{"value":"robust stability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894653$507CDB52-51B2-450A-93B2-945A8129D920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894653$74D206CA-7F2F-45CF-8E2E-50FAEDE050A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c26922f43444667253995419fc29207d93adea5","datavalue":{"value":"interval matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894653$D6234D80-CA8A-4720-A16B-2E627957B411","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":"Q1894653$CF766BC1-6305-47E2-A905-43DD7B8AE4F7","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":"Q1894653$701967BB-BD50-4AA7-8B2A-7EF896BEFF98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b713feeafcb25315a4a6aeb270b0e1447286a495","datavalue":{"value":{"entity-type":"item","numeric-id":4307419,"id":"Q4307419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$634BCFE0-9A41-407F-9FE3-11C68C272E02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14b19c740ad819740650a1eacb20114aec7f4f73","datavalue":{"value":{"entity-type":"item","numeric-id":3988971,"id":"Q3988971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$E6BD62FE-2BD1-4D24-B462-D9D028BA34FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0839e7e46510112865b452a6ed8d8dd889a4c60","datavalue":{"value":{"entity-type":"item","numeric-id":4058132,"id":"Q4058132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$E03679C5-16A7-4D07-B76C-59ADD775F166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c790a28a23b5ecff99b272336c89700604ca255","datavalue":{"value":{"entity-type":"item","numeric-id":3254327,"id":"Q3254327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$BDB97546-9656-449E-B111-1A9C135A47B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$EA64B078-638B-40EA-A01B-A31F125BC668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a98da500ea3b1afb498c4eb7809f38347ddbc32e","datavalue":{"value":{"entity-type":"item","numeric-id":1312298,"id":"Q1312298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$1A4F43D6-05E2-4A04-9D7D-B7DC350C6956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c001dd397cb92a2c48ebf13d0157bcc10fabd150","datavalue":{"value":{"entity-type":"item","numeric-id":3998722,"id":"Q3998722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$8DEC9F91-EAD8-42B4-8241-5A6253F02238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0648147ac11d50c0bd4253a5f95d5d06dd5bef4","datavalue":{"value":{"entity-type":"item","numeric-id":1802197,"id":"Q1802197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$452BBAA0-5DF9-4893-BC7C-EF3D574C4B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04699a42557872af9ce4a8b58bbf5eb889143561","datavalue":{"value":{"entity-type":"item","numeric-id":4742652,"id":"Q4742652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894653$F3A80C6E-55F2-44F3-8704-00505E134C2D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0951f160d2a5939f353bae3db3dc6652e98e9e19","datavalue":{"value":"https://doi.org/10.1007/bf01211520","type":"string"},"datatype":"url"},"type":"statement","id":"Q1894653$8D782347-6FB3-49C2-9348-E57896F8D2A2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a0d8d6851b2a14e74905a543ce2b979946b9242e","datavalue":{"value":"W2089575632","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894653$11BFC863-BC14-43C5-84AC-856EBA12ECB4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fdd0f5c1d72630827ab269c5a3767e1a8be2ee1","datavalue":{"value":{"entity-type":"item","numeric-id":1312298,"id":"Q1312298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22702d5aad3ad09288e6bc761df0108729307f2d","datavalue":{"value":{"amount":"+0.7914638519287109","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":"Q1894653$E379F158-9AD3-49D5-92D4-4693CEF5CDBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4824decc313c84f76f6c227d486110e5883f9aae","datavalue":{"value":{"entity-type":"item","numeric-id":3840413,"id":"Q3840413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80b53c96d60766e571832ed651d0917d98f0eeb2","datavalue":{"value":{"amount":"+0.781341016292572","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":"Q1894653$23A52F03-D117-4819-917C-5133B071D84A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9b006c9063d61d1730d5727565a3f7aee5089f0","datavalue":{"value":{"entity-type":"item","numeric-id":1898494,"id":"Q1898494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b462a26d015eaab544704897cafbc4121225ce05","datavalue":{"value":{"amount":"+0.7786707878112793","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":"Q1894653$774BA2B5-C064-44DC-83A6-427C8F43282B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f650230f53329bff5ff714b86c826f11640e6e03","datavalue":{"value":{"entity-type":"item","numeric-id":1913100,"id":"Q1913100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b462a26d015eaab544704897cafbc4121225ce05","datavalue":{"value":{"amount":"+0.7786707878112793","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":"Q1894653$C07864B6-4875-4028-BFDC-EF8146F2AC18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcd6560383b1cc4bf7cabcc5f8e916e8b2f24424","datavalue":{"value":{"entity-type":"item","numeric-id":1201158,"id":"Q1201158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e618a6e7ede02e32969b46673bbdc91e19767a7","datavalue":{"value":{"amount":"+0.776407778263092","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":"Q1894653$AFC62B6A-4718-4CCC-BFDC-B7F2BB6CE14A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_computational_complexity_of_approximating_the_minimal_perturbation_scaling_to_achieve_instability_in_an_interval_matrix"}}}}}