Matrix p-Norms Are NP-Hard to Approximate If p≠1,2,∞

We show that, for any rational p∈[1,∞) except $p=1,2$, unless $P=NP$, there is no polynomial time algorithm which approximates 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 which approximates the ∞,p mixed norm to some fixed relative precision.