IS CODE EQUIVALENCE EASY TO DECIDE

We study the computational difficulty of deciding whether two matrices generate equivalent linear codes, i.e., codes that consist of the sam e codewords up to a fixed permutation on the codeword coordinates. We call this problem Code Equivalence. Using techniques from the area of interactive proofs, we show on the one hand, that under the assumption that the polynomial-time hierarchy does not collapse, Code Equivalenc e is not NP-complete. On the other hand, we present a polynomial-time reduction from the Graph isomorphism problem to Code Equivalence. Thus if one could find an efficient (i.e., polynomial-time) algorithm for Code Equivalence, then one could settle the long-standing problem of d etermining whether there is an efficient algorithm for solving Graph I somorphism.