In this paper we study the hardness of the syndrome decoding problem over finite rings endowed with the Lee metric. We first prove that the decisional version of the problem is NP-complete, by a reduction from the 3-dimensional matching problem. Then, we study the actual complexity of solving the problem, by translating the best known solvers in the Hamming metric over finite fields to the Lee metric over finite rings, as well as proposing some novel solutions. For the analyzed algorithms, we assess the computational complexity in both the finite and asymptotic regimes.

翻译：在本文中,我们研究了与李氏度量的有限环相比综合症解码问题的严谨性。我们首先证明问题的决定版本是NP-完成的,减少了三维匹配问题。然后,我们研究了解决问题的实际复杂性,将Hamming衡量标准中已知的关于有限场的最著名的解决者转化为关于有限环的李氏度量,并提出了一些新颖的解决办法。对于分析的算法,我们评估了有限和无时效制度的计算复杂性。