On the subset sum problem over finite fields (Q958604): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 02:44, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the subset sum problem over finite fields |
scientific article |
Statements
On the subset sum problem over finite fields (English)
0 references
5 December 2008
0 references
The authors study the subset sum problem over finite fields which is known to be NP-complete. They study the number of solutions of the problem and in some cases obtain explicit or asymptotic formulas for the number of solutions. This problem has a natural application in the decoding of generalized Reed-Solomon codes using maximum likelihood decoding. Bounds are given in this case and deep holes are defined to be where the upper bound is met. The results of the paper are used to give some information as to when a vector is a deep hole.
0 references
subset sum problem
0 references
finite fields
0 references
decoding problem
0 references
Reed-Solomon codes
0 references
deep holes
0 references
asymptotic formulas for the number of solutions
0 references
explicit formulas
0 references
