Hard Problems of Algebraic Geometry Codes
Hard Problems of Algebraic Geometry Codes
复制标题
DOI：
10.1109/tit.2007.911213
复制
发表时间：
2005-07
影响因子：
2.5
通讯作者：
Qi Cheng
中科院分区：
文献类型：
--
作者：
Qi Cheng
最小距离是码的最重要的组合特征之一。最大似然译码问题是码的最重要的算法问题之一。虽然这些问题对于一般的线性码来说是困难的，但是用来证明其困难性的技术通常依赖于人工码的构造。一般来说，对特定类别的自然线性码的硬度知之甚少。在这封信中，我们表明，这两个问题是NP-困难的代数几何码。我们实现这一点，通过减少一个著名的NP完全问题，这些问题使用随机算法。在减少的代码的家庭是基于椭圆曲线。它们有正的速率，但字母表的大小是块长度的指数。
The minimum distance is one of the most important combinatorial characterizations of a code. The maximum-likelihood decoding problem is one of the most important algorithmic problems of a code. While these problems are known to be hard for general linear codes, the techniques used to prove their hardness often rely on the construction of artificial codes. In general, much less is known about the hardness of the specific classes of natural linear codes. In this correspondence, we show that both problems are NP-hard for algebraic geometry codes. We achieve this by reducing a well-known NP-complete problem to these problems using a randomized algorithm. The family of codes in the reductions is based on elliptic curves. They have positive rates, but the alphabet sizes are exponential in the block lengths.