smoking186 https://blog.hatena.ne.jp/smoking186/ 186 @ hatenablog https://186.hatenablog.com/ CS 符号 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… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20080224%2F1203856602" title=" RS符号のMLDはNP困難 - 186 @ hatenablog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2008-02-24 21:36:42 rich https://186.hatenablog.com/entry/20080224/1203856602 1.0 100%