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

共 8 条

[1] Combinatorial Nullstellensatz [J].

Alon, N .

COMBINATORICS PROBABILITY & COMPUTING, 1999, 8 (1-2) :7-29

[2]

Cheng Q, 2007, LECT NOTES COMPUT SC, V4484, P296

[3] On the list and bounded distance decodability of Reed-Solomon codes [J].

Cheng, Qi ;

Wan, Daqing .

SIAM JOURNAL ON COMPUTING, 2007, 37 (01) :195-209

[4] CYCLIC SPACES FOR GRASSMANN DERIVATIVES AND ADDITIVE THEORY [J].

DASILVA, JAD ;

HAMIDOUNE, YO .

BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 1994, 26 :140-146

[5]

Erdo P., 1980, Monographs of L'Enseignement Mathematique, V28

[6] THE REPRESENTATION OF SOME INTEGERS AS A SUBSET SUM [J].

HAMIDOUNE, YO .

BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 1994, 26 :557-563

[7]

LI YJ, SCI SINIC A IN PRESS

[8]

Petkovsek M., 1996, A = B

← 1 →