Computing the norm ∥A∥∞,1 is NP-hard∗
- 1 May 2000
- journal article
- research article
- Published by Taylor & Francis Ltd in Linear and Multilinear Algebra
- Vol. 47 (3), 195-204
- https://doi.org/10.1080/03081080008818644
Abstract
It is proved that computing the subordinate matrix norm ∥A∥∞1 is NP-hard, Even more, existence of a polynomial-time algorithm for computing this norm with relative accuracy less than 1/(4n2 ), where n is matrix size, implies P = NP.Keywords
This publication has 4 references indexed in Scilit:
- Complexity of Some Linear Problems with Interval DataReliable Computing, 1997
- Checking robust nonsingularity is NP-hardMathematics of Control, Signals, and Systems, 1993
- Algorithmes de calcul du maximum des formes quadratiques sur la boule unité de la norme du maximumNumerische Mathematik, 1984
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976