The question: Consider two norms N1 and N2 on the space of n-by-n complex matrices. N1 and N2 have the same isometry group and computing N1 is NP-HARD. Does it follow that computing N2 is NP-HARD as well?
Motivation for believing the answer is "yes": Consider the induced matrix p-norms. It is known that these norms are efficiently computable if and only if $p = 1,2,\infty$ (http://arxiv.org/abs/0908.1397). Similarly, the isometries of the induced p-norms are known as well (they are derived in this paper) and it turns out that there are three possible isometry groups: one group for $p = 1,\infty$, another group for $p = 2$, and a third group for every other $p \neq 1,2,\infty$.
So for the induced p-norms, the difficulty of computing the norm is directly related to the isometry goup. $p = 1,\infty$ is easiest to compute ($O(n^2)$ time) and they have the same isometry group. Next hardest is operator norm (still efficient: $O(n^3)$ time naively, possibly as low as $O(n^{2+\epsilon})$ time if the conjecture about matrix multiplication is true), which has an isometry group all its own. Finally, the norms for all other values of p share the same isometry group and are NP-HARD.
Similarly, all unitarily-invariant matrix norms are easy to compute (you only need to compute their singular values), and they all share one of two different isometry groups (either the Frobenius norm isometry group or the operator norm isometry group -- this is a result of A. Sourour).
Motivation for wanting an answer: Beyond providing another way of seeing that computing the induced p-norms for $p \neq 1,2,\infty$ is NP-HARD, there is a family of matrix norms in quantum information theory that we are investigating whose isometry groups are all equal. We know that computing one of the norms is NP-HARD, and we would very much like to be able to conclude that the rest of the norms are NP-HARD as well.
