{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,15]],"date-time":"2025-08-15T00:45:08Z","timestamp":1755218708549,"version":"3.43.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,2,1]],"date-time":"1997-02-01T00:00:00Z","timestamp":854755200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1997,2,1]],"date-time":"1997-02-01T00:00:00Z","timestamp":854755200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Reliable Computing"],"published-print":{"date-parts":[[1997,2]]},"DOI":"10.1023\/a:1009938325229","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T19:25:11Z","timestamp":1040585111000},"page":"51-81","source":"Crossref","is-referenced-by-count":8,"title":["NP-Hard Classes of Linear Algebraic Systems with Uncertainties"],"prefix":"10.1007","volume":"3","author":[{"given":"Anatoly V.","family":"Lakeyev","sequence":"first","affiliation":[]},{"given":"Vladik","family":"Kreinovich","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"130390_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-64971-4","volume-title":"Inequalities","author":"E. F. Beckenbach","year":"1961","unstructured":"Beckenbach, E. F. and Bellman, R.: Inequalities, Springer-Verlag, Berlin\u2013G\u00f6ttingen\u2013Heidelberg, 1961."},{"key":"130390_CR2","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"Cormen, Th. H., Leiserson, C. E., and Rivest, R. L.: Introduction to Algorithms, MIT Press, Cambridge, MA, and Mc-Graw Hill Co., N.Y., 1990."},{"key":"130390_CR3","volume-title":"Computers and Intractability: a Guide to the Theory of NPCompleteness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R. and Johnson, D. S.: Computers and Intractability: a Guide to the Theory of NPCompleteness, W. F. Freeman, San Francisco, 1979."},{"issue":"1","key":"130390_CR4","first-page":"191","volume":"20","author":"L. G. Khachiyan","year":"1979","unstructured":"Khachiyan, L. G.: A Polynomial-Time Algorithm for Linear Programming, Soviet Math. Dokl.\n20 (1) (1979), pp. 191\u2013194.","journal-title":"Soviet Math. Dokl."},{"key":"130390_CR5","volume-title":"Elements of the Theory of Functions and Functional Analysis","author":"A. N. Kolmogorov","year":"1972","unstructured":"Kolmogorov, A. N. and Fomin, S. V.: Elements of the Theory of Functions and Functional Analysis, Nauka Publ., Moscow, 1972 (in Russian)."},{"key":"130390_CR6","first-page":"6","volume":"1","author":"V. Kreinovich","year":"1993","unstructured":"Kreinovich, V., Lakeyev, A. V., and Noskov, S. I.: Optimal Solution of Interval Linear Systems is Intractable (NP-Hard), Interval Computations 1 (1993), pp. 6\u201314.","journal-title":"Interval Computations"},{"issue":"1","key":"130390_CR7","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0024-3795(94)00026-3","volume":"232","author":"V. Kreinovich","year":"1996","unstructured":"Kreinovich, V., Lakeyev, A. V., and Noskov, S. I.: Approximate Linear Algebra is Intractable, Linear Algebra and its Applications\n232 (1) (1996), pp. 45\u201354.","journal-title":"Linear Algebra and its Applications"},{"issue":"3","key":"130390_CR8","first-page":"518","volume":"47","author":"A. V. Lakeyev","year":"1993","unstructured":"Lakeyev, A. V. and Noskov, S. I.: A Description of the Set of Solutions of a Linear Equation with Interval Defined Operator and Right-Hand Side, Russian Acad. Sci. Dokl. Math.\n47 (3) (1993), pp. 518\u2013523.","journal-title":"Russian Acad. Sci. Dokl. Math."},{"issue":"5","key":"130390_CR9","first-page":"1074","volume":"35","author":"A.V. Lakeyev","year":"1994","unstructured":"Lakeyev, A.V. and Noskov, S. I.:On the Set of Solutions of the Linear Equationwith the Intervally Given Operator and the Right-Hand Side, Siberian Math. J.\n35 (5) (1994), pp. 1074\u20131084 (in Russian).","journal-title":"Siberian Math. J."},{"key":"130390_CR10","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/BF01386090","volume":"6","author":"W. Oettli","year":"1964","unstructured":"Oettli, W. and Prager, W.: Compatibility of Approximate Solution of Linear Equations with Given Error Bounds for Coefficients and Right-Hand Sides, Num. Math.\n6 (1964), pp. 405\u2013409.","journal-title":"Num. Math."},{"key":"130390_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01213466","volume":"6","author":"S. Poljak","year":"1993","unstructured":"Poljak, S. and Rohn, J.: Checking Robust Non-Singularity is NP-Hard,Mathematics of Control, Signals and Systems\n6 (1993), pp. 1\u20139.","journal-title":"Mathematics of Control, Signals and Systems"},{"key":"130390_CR12","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0024-3795(89)90004-9","volume":"126","author":"J. Rohn","year":"1989","unstructured":"Rohn, J.: Systems of Linear Interval Equations, Linear Algebra and its Applications\n126 (1989), pp. 39\u201378.","journal-title":"Linear Algebra and its Applications"},{"issue":"2","key":"130390_CR13","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1137\/S0895479893251198","volume":"16","author":"J. Rohn","year":"1995","unstructured":"Rohn, J. and Kreinovich, V.: Computing Exact Componentwise Bounds on Solutions of Linear Systems with Interval Data is NP-Hard, SIAM J. Matrix Anal. Appl.\n16 (2) (1995), pp. 415\u2013420.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"130390_CR14","first-page":"7","volume":"2","author":"S. P. Shary","year":"1991","unstructured":"Shary, S. P.: Optimal Solution of Interval Linear Algebraic Systems. I, Interval Computations 2 (1991), pp. 7\u201330.","journal-title":"Interval Computations"},{"issue":"4","key":"130390_CR15","first-page":"18","volume":"2","author":"S. P. Shary","year":"1992","unstructured":"Shary, S. P.:A New Class of Algorithms forOptimal Solution of Interval Linear Systems, Interval Computations 2 (4) (1992), pp. 18\u201329.","journal-title":"Interval Computations"},{"key":"130390_CR16","first-page":"179","volume-title":"Proc. of the Conference \u201cScientific Computation and Mathematical Modelling\u201d","author":"S. P. Shary","year":"1993","unstructured":"Shary, S. P.: Solving Interval Linear Systems with Nonnegative Matrices, in: Markov, S. M. (ed.), Proc. of the Conference \u201cScientific Computation and Mathematical Modelling\u201d, DATECS Publishing, Sofia, 1993, 179\u2013181."}],"container-title":["Reliable Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009938325229.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009938325229\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009938325229.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T09:32:13Z","timestamp":1754472733000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009938325229"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,2]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,2]]}},"alternative-id":["130390"],"URL":"https:\/\/doi.org\/10.1023\/a:1009938325229","relation":{},"ISSN":["1385-3139","1573-1340"],"issn-type":[{"type":"print","value":"1385-3139"},{"type":"electronic","value":"1573-1340"}],"subject":[],"published":{"date-parts":[[1997,2]]}}}