Avkodning av maxlikelihood är ett av de centrala algoritmiska problemen i kodningsteorin. Det har varit känt i över 25 år att maximal liknande avkodning av allmänna linjära koder är NP-hård. Ändå var det hittills okänt om maximal-likelihood avkodning förblir svårt för någon specifik familj av koder med icke-trivial algebraisk struktur. I den här tidningen bevisar vi att maximal liknande avkodning är NP-hård för familjen av Reed-Solomon-koder. Vi visar dessutom att maximal liknande avkodning av Reed-Solomon koder fortfarande är svårt även med obegränsad förbehandling, vilket stärker ett resultat av Bruck och Naor.
I allmänhet är dock den största sannolikheten för avkodning av GRS-koder NP-hård REF.
Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}