Abstrakt
It is proved that computing the subordinate matrix norm $\|A\|_{\infty,1}$ is NP-hard. Even more, existence of a polynomial-time algorithm for computing this norm with relative accuracy less than $1/(4n^2)$, where $n$ is matrix size, implies P=NP.