Computing the norm ∥A∥∞,1 is NP-hard∗
Jǐŕı Rohn · Linear and Multilinear Algebra · 2000
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.