On the subset sum problem over finite fields (Q958604)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the subset sum problem over finite fields |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8601319789886475
0 references
0.8555607199668884
0 references
0.8488243818283081
0 references
0.8248608112335205
0 references
0.8211756944656372
0 references
