Matrix P-norms are NP-hard to approximate if p ≠ 1,2,∞

Original · EN

We show that for any rational p ∈ [1,∞) except p = 1, 2, unless P = NP, there is no polynomial-time algorithm for approximating the matrix p-norm to arbitrary relative precision. We also show that for any rational p∈ [1,∞) including p = 1, 2, unless P = NP, there is no polynomial-time algorithm approximates the ∞, p mixed norm to some fixed relative precision.