For a $[n,k,nk+1]_q$ Reed Solomon code is there a polynomial time algorithm to find at least one minimum weight $(nk+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.

$\begingroup$ Presumably you don't know the generating matrix, but just the parameters. $\endgroup$– kodluJul 15, 2016 at 8:30

$\begingroup$ @kodlu even if you know $G$ it is not clear whether it would be able to find minimum weight codeword in polytime right? $\endgroup$– TurboJul 15, 2016 at 8:32
2 Answers
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 (nk)$. (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=nk+1$. That is because each row is nonzero, has weight at most $nk+1$, and is a codeword. The procedure described is certainly polynomial time.
In this paper some useful information is given, see the introduction and references. The problem of finding the weights is NPcomplete but not known to be NPhard. Without the generating matrix, the best known algorithms are exponential in complexity. If $G$ is known, I think it is still going to be exponential, but let me think a bit.
Edit The complete weight distribution is known for MDS codes. $A_i$ denotes number of codewords of weight $i$, $A_0=1,$ and $A_i=0,$ for $1\leq i \leq d1.$ The other nonzero weights are $$ A_i= \binom{n}{i} \sum_{j=0}^{id} (1)^{j}\binom{i}{j} \left( q^{i+1dj}1\right), $$ for $d\leq i \leq n.$ Letting $i=d$ gives $A_d=\binom{n}{d}(q1)$ minimum weight codewords out of $q^{nd+1}$ total codewords.
Edit 2 Actually any $k=nd+1$ positions in an MDS code is an information set, i.e. One can choose those positions freely. So choose say first $k1$ positions to be zero, the next to be $1$ and use $G$ to determine the rest of the coordinates, which all have to be nonzero. This gives a polynomial time algorithm, polynomial in $n$.


$\begingroup$ yes but a specific min weight codeword need not be that easy to find. $\endgroup$– kodluJul 15, 2016 at 9:21


$\begingroup$ also a decision problem is NPcomplete when it is both in NP and NPhard. $\endgroup$– TurboJul 15, 2016 at 10:20

$\begingroup$ hmm so how does this give a poly time alg for finding a min weight codeword? $\endgroup$– TurboJul 15, 2016 at 10:43