On the Hardness of Finding Permutation Automorphisms of Linear Codes

본문 미리보기

We study the hardness of finding permutation automorphisms of linear codes. We look into three main problems: $\mathsf{AUT}$, $\mathsf{AUT}$-$\mathsf{Gen}$ and $\mathsf{AUT}$-$\mathsf{Count}$ which, respectively, ask to find a non-trivial automorphism, a generating set and the order of the automorphism group. We give polynomial time reductions from $\mathsf{AUT}$ to $\mathsf{ISO}$ (the problem of finding a permutation isomorphism between two linear codes), and from $\mathsf{ISO}$ to $\mathsf{AU