A Search-to-Decision Reduction for the Permutation Code Equivalence Problem
Jean‐François Biasse, Giacomo Micheli · 2023
In this paper, we describe an efficient search-to-decision reduction for the permutation code equivalence problem. Given two linear codes ${\mathcal{C}_1}$, ${\mathcal{C}_2}$ of length n and dimension k over ${\mathbb{F}_q}$, we describe an algorithm that finds $\pi \in {\mathcal{S}_n}$ such that $\pi \left( {{\mathcal{C}_1}} \right) = {\mathcal{C}_2}$ by using a polynomial number of queries to an oracle that decides whether two codes are permutation-equivalent.