MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IF p not equal to 1, 2, infinity
We show that, for any rational p ∈ [1,∞) [p is an element of the set [1, infinity)] 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,∞) [p is an element of the set...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2011
|
| Online Access: | http://hdl.handle.net/1721.1/64956 |
| Summary: | We show that, for any rational p ∈ [1,∞) [p is an element of the set [1, infinity)] 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,∞) [p is an element of the set [1, infinity)] including p = 1, 2, unless P = NP, there is no polynomialtime
algorithm which approximates the ∞, p [infinity, p] mixed norm to some fixed relative precision. |
|---|