NP-Complete Problems for Lee Metric Codes
Violetta Weger, Paolo Santini, Massimo Battaglioni, Anna-Lena Trautmann · arXiv (Cornell University) · 2020
We consider codes over finite rings endowed with the Lee metric and prove the NP-completeness of the associated syndrome decoding problem (SDP). Then, we study the best known algorithms for solving the SDP, which are information set decoding (ISD) algorithms, and generalize them to the Lee metric case. Finally we assess their complexity for a wide range of parameters.