We give a randomized reduction for the Rank Syndrome Decoding problem and Rank Minimum Distance problem for rank codes over extension fields. Our results are based on embedding linear codes in the Hamming space into linear codes over an extension field equipped with the rank metric. We prove that if any of the previous problems for the rank metric is in ZPP = RP∩coRP, then we would have NP = ZPP. We also give complexity results for the respective rank metric approximation problems.
No takes yet. Share an insight, caveat, or question.
Gaborit et al. (2016) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: