Matrix P-norms are NP-hard to approximate if p \neq 1,2,\infty

Julien M. Hendrickx, Alex Olshevsky

We show that for any rational p \in [1,\infty) except p = 1, 2, unless P = NP, there is no polynomial-time algorithm for approximating the matrix p-norm to arbitrary relative preci…