Matrix P-norms are NP-hard to approximate if p ≠1,2,∞
Julien M. Hendrickx, Alex Olshevsky · arXiv (Cornell University) · 2009
Abstract. 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. 1. Introduction. The