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 条
  • [1] The k-subset sum problem over finite fields
    Wang, Weiqiong
    Nguyen, Jennifer
    FINITE FIELDS AND THEIR APPLICATIONS, 2018, 51 : 204 - 217
  • [2] On the subset sum problem for finite fields
    Pavone, Marco
    FINITE FIELDS AND THEIR APPLICATIONS, 2021, 76
  • [3] The k-subset sum problem over finite fields of characteristic 2
    Choe, Hyok
    Choe, Chunghyok
    FINITE FIELDS AND THEIR APPLICATIONS, 2019, 59 : 175 - 184
  • [4] An approach to the moments subset sum problem through systems of diagonal equations over finite fields
    Gottig, Juan Francisco
    Perez, Mariana
    Privitelli, Melina
    FINITE FIELDS AND THEIR APPLICATIONS, 2024, 100
  • [5] ON SUM OF PRODUCTS AND THE ERDOS DISTANCE PROBLEM OVER FINITE FIELDS
    Vinh, Le Anh
    BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2011, 84 (01) : 1 - 9
  • [6] The subset sum problem for finite abelian groups
    Kosters, Michiel
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2013, 120 (03) : 527 - 530
  • [7] Laced Boolean functions and subset sum problems in finite fields
    Canright, David
    Gangopadhyay, Sugata
    Maitra, Subhamoy
    Stanica, Pantelimon
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (11) : 1059 - 1069
  • [8] Moment subset sums over finite fields
    Lai, Tim
    Marino, Alicia
    Robinson, Angela
    Wan, Daqing
    FINITE FIELDS AND THEIR APPLICATIONS, 2020, 62
  • [9] Subset sums of quadratic residues over finite fields
    Wang, Weiqiong
    Wang, Li-Ping
    Zhou, Haiyan
    FINITE FIELDS AND THEIR APPLICATIONS, 2017, 43 : 106 - 122
  • [10] On variations of the subset sum problem
    Alfonsin, JLR
    DISCRETE APPLIED MATHEMATICS, 1998, 81 (1-3) : 1 - 7
12345