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 条
  • [21] THE MINIMUM RANK PROBLEM OVER FINITE FIELDS
    Grout, Jason
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2010, 20 : 691 - 716
  • [22] ON THE SUBSET SUM PROBLEM IN BRANCH GROUPS
    Nikolaev, Andrey
    Ushakov, Alexander
    GROUPS COMPLEXITY CRYPTOLOGY, 2020, 12 (01)
  • [23] The equal–sum–free subset problem
    Gábor Bacsó
    Zsolt Tuza
    Acta Scientiarum Mathematicarum, 2020, 86 : 73 - 79
  • [24] Subset sum problem in polycyclic groups
    Nikolaev, Andrey
    Ushakov, Alexander
    JOURNAL OF SYMBOLIC COMPUTATION, 2018, 84 : 84 - 94
  • [25] ON THE EQUAL-SUBSET-SUM PROBLEM
    WOEGINGER, GJ
    YU, ZL
    INFORMATION PROCESSING LETTERS, 1992, 42 (06) : 299 - 302
  • [26] An exact algorithm for the subset sum problem
    Soma, NY
    Toth, P
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 136 (01) : 57 - 66
  • [27] Approximability of the Subset Sum Reconfiguration Problem
    Ito, Takehiro
    Demaine, Erik D.
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011, 2011, 6648 : 58 - 69
  • [28] The Subset Sum Problem in Keno Modelling
    Sugden, Stephen J.
    NUMERICAL ANALYSIS AND APPLIED MATHEMATICS, 2008, 1048 : 526 - 529
  • [29] Approximability of the subset sum reconfiguration problem
    Takehiro Ito
    Erik D. Demaine
    Journal of Combinatorial Optimization, 2014, 28 : 639 - 654
  • [30] An Optical Solution for the Subset Sum Problem
    Hasan, Masud
    Hossain, S. M. Shabab
    Rahman, Md. Mahmudur
    Rahman, M. Sohel
    NATURAL COMPUTING, 2010, 2 : 165 - 173
12345