{"entities":{"Q676167":{"pageid":678016,"ns":120,"title":"Item:Q676167","lastrevid":63501057,"modified":"2026-04-11T13:35:03Z","type":"item","id":"Q676167","labels":{"en":{"language":"en","value":"Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 992028"}},"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":"Q676167$B2CEF50A-6F88-4DF8-977A-E4425D400CCE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d8f570b17131290fb4299995664d3f8324762966","datavalue":{"value":{"text":"Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q676167$EDF2F2FE-BFF8-4381-A0A7-D9BCE96A9C83","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b162eef6c94be1f48923cbf034632182576adccb","datavalue":{"value":"0871.65022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676167$D18C8FCB-D3B1-4819-AE53-F1798B453B38","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"77361b23cec60074d11bf28d1c6fd0a50ba55510","datavalue":{"value":"10.1007/BF02389894","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676167$D8423C0E-CD42-448B-A0F7-D649910AA7EB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2498ed7cf3607871ad6e64c348055a3c8fc89172","datavalue":{"value":{"entity-type":"item","numeric-id":592003,"id":"Q592003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$510A817E-D857-4C3C-B6B8-2471B4D6CEC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"acc293918b743e94faa2c614ca0fde8fd9ed697f","datavalue":{"value":{"entity-type":"item","numeric-id":1276133,"id":"Q1276133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$6393DF99-6400-46E0-8E62-439DAE24937E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c7999e3e01d43838ac559f475f3b198149793512","datavalue":{"value":{"entity-type":"item","numeric-id":163536,"id":"Q163536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$8203D962-52FC-4552-B629-3C69BFAE9780","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1c0636d1f8183c1e3e3dfb36c3e7a25a96aaad60","datavalue":{"value":{"time":"+1997-10-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q676167$8300E003-0560-4D2D-85ED-09741C0B5AFC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0f6bba900a16a845aeaeacb2985854929c68f3ca","datavalue":{"value":"Let \\(A\\) be a quadratic interval matrix which is strongly regular and which has rational bounds. It is further assumed that for each \\(\\delta>0\\) there exists a polynomial time algorithm which solves the interval equation \\(Ax=b\\) for any interval vector \\(b\\) with rational coefficients within relative or absolute accurracy \\(\\delta\\). Then it is shown that \\(P=NP\\). This result holds also under the additional restriction that \\(A\\) is symmetric.","type":"string"},"datatype":"string"},"type":"statement","id":"Q676167$89D12340-6DA3-4645-A719-1C11B48A9F87","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9cc9b08ea134d5bef9e23d7e8fde5198cfcf8933","datavalue":{"value":{"entity-type":"item","numeric-id":593285,"id":"Q593285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$E42F5EF8-EE49-4E82-9AFE-228A9C1AC5D0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9e4257514d9fd4eac10996fc6305328b84fd9c9b","datavalue":{"value":"65F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676167$B769F584-2ECD-4349-8A10-B1C0C07A00D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676167$8B0C0217-8E29-4477-AE55-ECF4CFE8B745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4d2aa49789d35e35613e1a84ce4788bfee1559e6","datavalue":{"value":"65G30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676167$8DE19C0F-4B21-430D-AA5E-0FE5A5E043DA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"48a7012bc46fd1a5c5e1c7e7e3d7e676d93e35c7","datavalue":{"value":"992028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q676167$7B12BEF4-7175-46A6-86A5-1589CE16BBC5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bea72e7ec1ed4cc96ce6ad0106e7856140a67e39","datavalue":{"value":"linear interval equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q676167$A413AC39-2B98-4A02-A1CA-74FF55B81E32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q676167$56BBE0D4-0BC2-454B-A712-6605E28D10A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e20b89ac6aaa0a2ba9ea3bf6d528b763c620b312","datavalue":{"value":"inclusion of solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q676167$91D7AB2C-173F-43F5-BC66-334FB48A423D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b44e0460de8b89a3695e54806f9b749b49a67a49","datavalue":{"value":"interval arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q676167$87A78D62-10C2-49C4-BCD0-1773D432B6C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q676167$38F748A3-9006-4F50-8E5D-57E3561B3D2F","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":"Q676167$3227ADFC-1E10-4334-BC9D-C6F1DB97D9DC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e57db85c69b9b7fb9693a309e1c263031aedb4e","datavalue":{"value":{"entity-type":"item","numeric-id":4857581,"id":"Q4857581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$58BD4A51-4D89-4A9A-80D9-2DAAAE689CAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d096ad35c32662be4596601668d001e2923907a5","datavalue":{"value":{"entity-type":"item","numeric-id":3345690,"id":"Q3345690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$B1D10FBD-5B14-4589-88D9-C6A153FE446C","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":"Q676167$A733C045-4FC9-44FD-A9EF-0922488CF08A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99c6c9e429ffa35c152980ca6e8bb6bf9dddd9ab","datavalue":{"value":{"entity-type":"item","numeric-id":806948,"id":"Q806948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$BA73B824-234B-4F93-B68F-0BF4824CC67A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"869734d82d21e8e3791373ce68df5919a10a6004","datavalue":{"value":{"entity-type":"item","numeric-id":4851401,"id":"Q4851401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$5D95B476-F33E-4EA8-AEB1-336C224D42D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fae9af266c14e7ccd05d174e78e3931b78285683","datavalue":{"value":{"entity-type":"item","numeric-id":1906787,"id":"Q1906787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$83E9214A-A00B-404A-BE95-0F4BB14C6DE1","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":"Q676167$363F07F1-89E8-41E5-BCD5-53CE1E4E7BBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abf3cc8d4e09eae09ce0c5f0153e2eb9eca3664d","datavalue":{"value":{"entity-type":"item","numeric-id":4874515,"id":"Q4874515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$9566856D-F177-4C5E-9BDC-E3589DE2942D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb75f9611d9c678d361c3089796d10b2abd32c26","datavalue":{"value":{"entity-type":"item","numeric-id":4835403,"id":"Q4835403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q676167$829FEC69-BE1C-4FBB-90B1-B47197F7CCF8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6be9d2caf810fbf58d8cea147bc92771fc06e69","datavalue":{"value":{"entity-type":"item","numeric-id":4874515,"id":"Q4874515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f91f6ecfe95998891da5cea61dcddef935469d1","datavalue":{"value":{"amount":"+0.9391459226608276","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":"Q676167$11D72407-9D6F-4B1E-B552-5A3883E361A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f2363e0bdb7e1f4ee252015eaf42ce639c3c3b9","datavalue":{"value":{"entity-type":"item","numeric-id":1340883,"id":"Q1340883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54b99b9661d95be99c532d7dea4adcdaa618a561","datavalue":{"value":{"amount":"+0.8871612548828125","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":"Q676167$9AE38A00-50CE-41C2-BB56-2606DEE08A96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f06f6a5891afd45548c06a5762f832eedfdc9b25","datavalue":{"value":{"entity-type":"item","numeric-id":1894514,"id":"Q1894514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d14b3c8df2e9e88ad76cbfda02d87ff212a51fcd","datavalue":{"value":{"amount":"+0.8498097658157349","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":"Q676167$21BF8D57-E0A3-4C92-A513-1D1B3959EF8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7cec941066543b0db1f158a782a1fc3c93254f7","datavalue":{"value":{"entity-type":"item","numeric-id":4835403,"id":"Q4835403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d5df1924e23c4543e6e5c5535a7543d2d3e0732","datavalue":{"value":{"amount":"+0.8361614346504211","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":"Q676167$14FD5B75-E854-40C3-91B6-6224892553BB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Linear_interval_equations:_Computing_enclosures_with_bounded_relative_or_absolute_overestimation_is_NP-hard"}}}}}