Complexity of the Frobenius problem |
| |
| Authors: | J L Ramírez-Alfonsín |
| |
| Institution: | (1) Instituto de Matemáticas, Universidad Nacional Autónoma de México, Area de la Investigación Científica Circuito Exterior, Ciudad Universitaria, 04510 México D.F. |
| |
| Abstract: | Consider the Frobenius Problem: Given positive integersa
1,...,a
n witha
i  2 and such that their greatest common divisor is one, find the largest natural number that is not expressible as a non-negative integer combination ofa
1,...,a
n. In this paper we prove that the Frobenius problem is NP-hard, under Turing reductions. |
| |
| Keywords: | 68 Q 15 90 C 10 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
