RS符号のMLDはNP困難

Guruswami and Vardy “Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-hard” (SODA 2005).
MLDは最尤復号でいいんだったかな.
MLD-LinearとはF_q要素のm×n行列とシンドロームsと正整数wを入力として, Hv^t=s^tかつハミング重みがw以下となるn次のF_q要素のエラーベクトルvが存在するかどうかを答える問題. またの名をSyndrome Decoding Problemと言う. (Stern93やStern96では, この名前だった.)
Berlekamp, McEliece, and van Tilborg (IEEE IT '78)によってNP完全であることが知られている. Bruck and NaorやLobsteinによって1990年にはMLD-Linear with PreprocessingでもNP完全であることが示されている. Arora, Babai, Stern, and Sweedykはwが定数であってもMLD-LinearがNP完全であることを示した. また, Feige and MicciancioとRegevはMLD-Linear with Preprocessingの3-ε近似がNP困難であることを示している.
さて様々な結果が並ぶわけだが, これらは全て線形符号にしか限定していない. もっと小さなクラスだとどうなるのか?というのは未解決問題だった. なのでReed-Solomon符号でやってみた, というのがこの結果. BMvT78と同様に, Three-Dimensional Matchingからの帰着を構成している. ただしF_qのq=2^rのタイプについてのみ. また, n=qの場合はまだ構成出来ていないようだ.
ということなので, 巡回符号/BCH符号の場合に関する構成を考えると面白いと思いました.