For a $[n,k,n-k+1]\_q$ Reed Solomon code is there a polynomial time algorithm to find at least one minimum weight $(n-k+1)$ codeword? I searched in literature and I could not find one and hence I am suspecting there is a decision version of this problem which might be $\mathsf{NP}$-complete.



Finding minimum weight codeword of MDS RS code
The solution holds for any MDS code. I'm assuming the code is given by its generator matrix $G$. In that case, simply convert $G$ into its reduced row echelon form $G'$. This will be a matrix of the form $G'=[I | A]$, where $I$ is the $k\times k$ identity matrix, and $A$ is $k\times (n-k)$. (Note here: since the code is MDS, every $k$ columns of $G$ are linearly independent, and there is no need to permute columns) It is now easy to see each and every row of $G'$ is a codeword of weight $d=n-k+1$. That is because each row is non-zero, has weight at most $n-k+1$, and is a codeword. The procedure described is certainly polynomial time.


