On the subset sum problem over finite fields

被引：71
|
作者：
Li, Jiyou [1 ]
Wan, Daqing [2 ]
机构：
[1] Peking Univ, Sch Math Sci, Beijing 100871, Peoples R China
[2] Univ Calif Irvine, Dept Math, Irvine, CA 92697 USA
来源：
FINITE FIELDS AND THEIR APPLICATIONS | 2008年 / 14卷 / 04期
基金：
中国国家自然科学基金;
关键词：
Subset sum problem; Finite fields; Decoding problem; Reed-Solomon codes; Deep holes;
D O I：
10.1016/j.ffa.2008.05.003
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The subset sum problem over finite fields is a well-known NP-complete problem. It arises naturally from decoding generalized Reed-Solomon codes. In this paper, we study the number of solutions of the subset sum problem from a mathematical point of view. In several interesting cases, we obtain explicit or asymptotic formulas for the solution number. As a consequence, we obtain some results on the decoding problem of Reed-Solomon codes. (C) 2008 Elsevier Inc. All rights reserved.
引用
收藏
页码：911 / 929
页数：19
相关论文
共 50 条
12345